子数组的最大和及系列问题

子数组的最大累加和问题

给定一个数组arr，返回子数组的最大累加和。
例如，arr=[1,-2,3,5,-2,6,-1]，所有的子数组中，[3,5,-2,6]可以累加出最大的和12，所以返回12。

思路

时间复杂度O(n)
使用max记录当前和的最大值和sum记录当前的和

  • sum < 0 -> 舍弃前面的，sum = 当前值
  • sum >= 0 -> 累加
    每次更新完sum，要更新max

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public static int getMaxSum(int[] a) {
	//记录当前的和
	int sum = 0;
	//记录最大值
	int maxNum = Integer.MIN_VALUE;
	for (int i = 0; i < a.length; i++) {
		//如果和小于0，说明加上正数或会变大，但是仍然起副作用
		//因此直接丢掉，使得sum为当前值，注意不是0，因为可能所有数字都是负数
		if (sum < 0) {
			sum = a[i];
		} else {
			//和大于0，可以继续累加
			sum += a[i];
		}
		//每次算完和，要更新max，这样才能记录下最大值
		maxNum = Math.max(maxNum, sum);
	}
	return maxNum;
}

找到两个不相容子数组的最大和

给定一个数组arr，其中有很多的子数组，找到两个不相容子数组使得相加的和最大，并返回和的最大值。
比如，数组[1,-1,0,-2,3,5,-2,8,7,-4]，两个不相容子数组分别为[3,5]和[8,7]时累加和最大，所以返回23。
再比如，数组[3,-1,0,-2,3,5,-2,8,7,-4]，两个不相容子数组分别为[3]和[3,5,-2,8,7]时累加和最大，所以返回24。

思路

借鉴上面的思路，做一些变形
设置两个数组

  • left[i]表示[0,i]上的子数组最大和
  • right[i]表示[i,N-1]上子数组的最大和

然后设置分割点k分别计算left[k]+right[k+1]最大值
该值表示[0,i]和[i+1,N-1]中最大值的和，既保持了不相交，也算出了最大值

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
public static int getUnconnetedSum(int[] a){
	int[] left = new int[a.length];
	int[] right = new int[a.length];
	int sum = 0;
	int maxNum = Integer.MIN_VALUE;
	//用求子数组最大和方法初始化left
	for (int i = 0; i < a.length; i++) {
		if(sum < 0){
			sum = a[i];
		}else{
			sum += a[i];
		}
		maxNum = Math.max(maxNum, sum);
		left[i] = maxNum;
	}
	sum = 0;
	maxNum = Integer.MIN_VALUE;
	//用求子数组最大和方法初始化right
	for(int i = a.length-1; i >= 0; i--){
		if(sum < 0){
			sum = a[i];
		}else{
			sum += a[i];
		}
		maxNum = Math.max(maxNum, sum);
		right[i] = maxNum;
	}
	
	int res = Integer.MIN_VALUE;
	//以i为分界点，查找最大值
	for (int i = 0; i < a.length-1; i++) {
		res = Math.max(res, left[i]+right[i+1]);
	}
	return res;
}

子矩阵的最大累加和问题

给定一个矩阵matrix，其中的值有正、有负、有0，返回子矩阵的最大累加和。 例如，矩阵matrix为：
-90 48 78
64 -40 64
-81 -7 66
其中，最大累加和的子矩阵为：
48 78
-40 64
-7 66
所以返回累加和209。

再例如，matrix为：
-1 -1 -1
-1 2 2
-1 -1 -1
其中最大累加和的子矩阵为：
2 2
所以返回累加和 4。

思路

利用最大子数组求和的思想
先用tmp[i]求出在该行i列上所有数字的和，是一个列加的和，不停的用上一行列加tmp
有了tmp再求最大子数组和，就是求出选那些列能组成最大和
为了遍历所有的行，需要设置分割点，即先遍历0123…N,然后123…N,234..N
把所有可能都遍历到

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public static int getMaxtrixSum(int[][] a) {	
	int maxNum = Integer.MIN_VALUE;
	//分割点i，遍历所有的行
	for(int i = 0; i < a.length; i++){
		//存放该行以上所有的和，即tmp[i]表示i列在该行的所有值的和
		int[] tmp = new int[a[0].length];
		//可遍历第012，12，2行
		for(int k = i; k < a.length; k++){
			//求最大子数组和的过程
			int curSum = 0;
			for(int j = 0; j < a[0].length; j++){
				//先更新tmp，然后求最大
				tmp[j] += a[k][j];
				if(curSum < 0){
					curSum = tmp[j];
				}else{
					curSum += tmp[j];
				}
				maxNum = Math.max(curSum, maxNum);
			}
		}
	}
	return maxNum;
}