欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

连续子序列求和的最大值

程序员文章站 2022-03-06 18:04:28
...

输入一个整数序列(浮点数序列也适合本处讲的算法),求出其中连续子序列求和的最大值。
连续子序列求和的最大值
连续子序列求和的最大值

public static int maxLength(int []arr,int k)
	{
		if(arr==null||arr.length==0)
		{
			return 0;
		}
		HashMap<Integer,Integer>map=new HashMap<Integer,Integer>();
		map.put(0, -1);
		int len=0;
		int sum=0;
		for(int i=0;i<arr.length;i++)
		{
			sum+=arr[i];
			if(map.containsKey(sum-k)) {
				len=Math.max(i-map.get(sum-k), len);
			}
			if(!map.containsKey(sum)) {
				map.put(sum, i);
			}
		}
		return len;
	}

连续子序列求和的最大值
连续子序列求和的最大值

public static int mostEOR(int []arr)
	{
		int ans=0;
		int xor=0;
		int []mosts=new int [arr.length];
		HashMap<Integer,Integer>map=new HashMap<>();
		map.put(0, -1);
		for(int i=0;i<arr.length;i++)
		{
			xor^=arr[i];//异或和
			if(map.containsKey(xor)) {
				int pre=map.get(xor);
				//出现异或和为0的位置,这是属于第二种情况
				//pre==-1表明没有数字,只有1个异或和0的数组
				mosts[i]=pre==-1?1:(mosts[pre]+1);
			}
			if(i>0) {
				//第一种情况,最后一块异或和不为0
				mosts[i]=Math.max(mosts[i-1], mosts[i]);
			}
			map.put(xor, i);
			ans=Math.max(ans, mosts[i]);
		}
		return ans;
	}
相关标签: 面试