首页 > 剑指offer > 连续子数组(二维)的最大和
2015
10-10

连续子数组(二维)的最大和

一维数组的连续子数组的最大和

题目:输入一个整型数组,数组里有正数也有负数。数组中一个或连续的多个整数组成一个子数组。求所有子数组的和的最大值。要求时间负责度为O(n)。

假如输入数组为{1,-2,3,10,-4,7,2,-5},我们尝试从头到尾累加其中的正数,初始化和为0,第一步加上1,此时和为1,第二步加上-2,此时和为-1,第三步加上3,此时我们发现-1+3=2,最大和2反而比3一个单独的整数小,这是因为3加上了一个负数,发现这个规律以后我们就重新作出累加条件:如果当前和为负数,那么就放弃前面的累加和,从数组中的下一个数再开始计数。

剑指offer和编程之美都有此题。参考这里:剑指offer(14)-最大子向量和 九度1372。算法可以优化为下面的几行代码:

	static int MaxSum(int arr[], int n){
		int currentSum = arr[0];
		int ans = currentSum;
		for(int i=1; i<n; i++){
			currentSum = Math.max(currentSum+arr[i], arr[i]);
			ans = Math.max(ans, currentSum);
		}
		return ans;
	}

二维数组的连续子数组的最大和

二维数组的连续子数组即为一个矩阵,如下图所示

rectangle-11

设矩阵的坐上顶点为A(i,j), 右下顶点为 B(endi, endj). 在图中即为 A(1,1), B(3,3)。我们可以用Rect(A,B)即 (1,1,3,3,)来表示矩形区域。

1. 方法1:直接计算

我们可以遍历所有的矩形区域,找出其中的最大值,其中遍历的话复杂度为O(M^2 * N^2),假设二维数组为M行N列。

其中怎么计算子矩阵的和呢?通过预处理,我们可以再O(1)的时间内算出。具体看下面的代码:

arrSum函数即做预处理,得到数组p,p[i][j]表示已Rect(0, 0, i-1, j-1)矩形区域的总和。有了p数组就可以直接计算出任意矩形的总和。

	public static int[][] arrSum(int arr[][]){
		int m = arr.length;
		int n = arr[0].length;
		int p[][] = new int[m+1][n+1];
		p[0][0] = arr[0][0];
		for(int i=0; i<=m; i++) p[i][0] = 0;
		for(int i=0; i<=n; i++) p[0][i] = 0;
		for(int i=1; i<=m; i++){
			for(int j=1; j<=n; j++){
				p[i][j] = p[i-1][j] + p[i][j-1] + arr[i-1][j-1] - p[i-1][j-1];
			}
		}
		return p;
	}
	//遍历所有二维数组的矩形区域
	static int  maxArrSum(int arr[][]){
		int m = arr.length;
		int n = arr[0].length;
		int p[][] = arrSum(arr);
		int ans = Integer.MIN_VALUE;
		for(int i=1; i<=m; i++){
			for(int j=1; j<=n; j++){
				for(int endi=i; endi <=m; endi++){
					for(int endj=j; endj<=n; endj++){
						int sum = p[endi][endj] - p[i-1][endj] - p[endi][j-1] + p[i-1][j-1];
						if(ans < sum) ans = sum;
					}
				}
			}
		}
		return ans;
	}

2. 方法二 转化为一维数组计算

这里并不是把整个二维数组转化为一维的,而是说把部分连续的行合并,看成是一行计算。这样枚举所有连续的行,把这些连续的行看成是一个整体,把一列看成是一个数字,问题就转化为上面的一维数组的算法了。还可以采用上面的预处理方法,在O(1)的时间内计算出任意一列的和。代码如下,colSum函数即为预处理函数,我们还可以根据M,N的大小做些优化。算法的复杂度为 O(N * M * min(M,N) ).

	//求一维数组的最大连续和
	static int maxSum(int p[][], int startLine,int endLine,int n){
		int ans = p[endLine][1] - p[startLine-1][1]; //即第一个列(startLine行到endLine行)的和
		int cmax = ans;
		for(int i=2; i<=n; i++){
			int ci = p[endLine][i] - p[startLine-1][i];
			cmax = Math.max(cmax+ci, ci);
			ans = Math.max(cmax, ans);
		}
		//System.out.println(startLine + " " + endLine + " " +ans);
		return ans;
	}

	static int[][] colSum(int arr[][]){
		int m = arr.length;
		int n = arr[0].length;
		int  p[][] = new int[m+1][n+1];
		for(int i=1; i<=m; i++)
			for(int j=1; j<=n; j++)
				p[i][j] = p[i-1][j] + arr[i-1][j-1];
		return p;
	}

	static int maxArrSum2(int arr[][]){
		int m = arr.length;
		int n = arr[0].length;
		if(m > n){
			//对数组进行逆置
			arr = reverseArr(arr);
			int tmp = m;
			m = n;
			n = tmp;
		}
		int p[][] = colSum(arr);
		int tempMax = Integer.MIN_VALUE;

		//h表示当前矩阵的高度. 即把多少行合并为一行看
		for(int h=1; h<=m; h++){
			for(int i=1; i+h-1 <= m; i++){
				int endLine = i+h-1;
				//转化为长度为n一维数组,复杂度为O(n)
				tempMax = Math.max(tempMax, maxSum(p, i, endLine, n));
			}
		}
		return tempMax;
	}

	static int[][] reverseArr(int arr[][]){
		int m = arr.length;
		int n = arr[0].length;
		int newArr[][] = new int[n][m];
		for(int i=0; i<m; i++)
			for(int j=0; j<n; j++)
				 newArr[j][i] = arr[i][j];
		return newArr;
	}

	public static void main(String[] args) {
		int arr[][] = {{1, 2, -1, -4, -20},
                {-8, -3, 4, 2, 1},
                {3, 8, 10, 1, 3},
                {-4, -1, 1, 7, -6}
               };

		int ans = maxArrSum(arr);
		System.out.println("method 1: " + ans);
		ans = maxArrSum2(arr);
		System.out.println("method 2: " + ans);
	}

 扩展问题

如果二维数组首尾相连,如何计算?

可以先考虑一维数组首位相连的问题。一个方法是把原来的数组进行扩充,例如对于 arr[0 ... n-1 ] 可以看成是  arr[0 ... n-1, 0, 1, ....n-2]。即原数组的长度由原来的n,变为了 2*n-1。实际中计算中没有必要扩充,求余即可。需要注意的是,如果全部都是非负的,我们需要加一个判断,防止计算结果超出数组的总和。当然还有其他的计算方法,大家可以参考编程之美一书。

static int MaxSumLinked(int arr[], int n){
		int currentSum = arr[0];
		int ans = currentSum;
		boolean hasNegative = false;//有可能全部都是非负,这时就没必要往后计算
		for(int i=1; i<n*2-1; i++){
			if(i < n && arr[i] < 0) hasNegative = true;
			currentSum = Math.max(currentSum+arr[i%n], arr[i%n]);
			ans = Math.max(ans, currentSum);
			if(i == n-1 && !hasNegative) return ans;
		}
		return ans;
	}

二维数组的计算方法和这个类似。