首页 > 代码库 > 编程之美2.15 二维数组最大子数组的和(数组下标从(1,1)开始)
编程之美2.15 二维数组最大子数组的和(数组下标从(1,1)开始)
首先,我们看到这篇文章的题目,我们就会想到之前的那个题目 -- 连续子数组最大和问题。这个问题无疑就是把原问题扩展到二维的情况。
想起来这个问题也不是很难,我们可以求解一维矩阵的思想,即我们可以固定住行(或列),之后,我们去求解列(或行)所构成的最大和就可以了。
这里的解法利用的是固定住行,然后求解需要寻找的列之和,利用书中提到的一个公式:
以左上角的元素(1,1)和当前元素(i,j)为顶点对的子矩阵的部分和,部分和的计算如下
PS[i][j] = A[i][j]+PS[i-1][j]+PS[i][j-1]-PS[i-1][j-1]
由此,我们很容易可以得到下面的解答:
函数声明:
/*2.15 二维数组最大子数组的和(数组下标从(1,1)开始)*/ int DutPartialSum(int**, int, int, int); int DutMaxSubMatrixInTwoDimensionArray(int**, int, int);
源代码:
bool _DutPartialSum = false; int DutPartialSum(int** p, int i, int j, int k) { if (!p || i <= 0 || j <= 0 || k <= 0) { _DutPartialSum = true; return -1; } return p[j][k] - p[j][k - 1] - p[i - 1][k] + p[i - 1][k - 1]; } bool _DutMaxSubMatrixInTwoDimensionArray = false; int DutMaxSubMatrixInTwoDimensionArray(int** A, int n, int m) { if (!A || n <= 0 || m <= 0) { _DutMaxSubMatrixInTwoDimensionArray = true; return -1; } int **p = new int* [n + 1]; for (int i = 0; i <= n; ++i) p[i] = new int[m]; for (int i = 0; i <= n; ++i) p[i][0] = 0; for (int i = 0; i <= m; ++i) p[0][i] = 0; for (int i = 1; i <= n; ++i) for (int j = 1; j <= m; ++j) p[i][j] = p[i - 1][j] + p[i][j - 1] - p[i - 1][j - 1] + A[i][j]; int maxSum = 1 << 31; for (int i = 1; i <= n; ++i) { for (int j = i; j <= n; ++j) { int start = DutPartialSum(p, i, j, m); int all = DutPartialSum(p, i, j, m); for (int k = m - 1; k >= 1; --k) { if (start <= 0) start = DutPartialSum(p, i, j, k); else start += DutPartialSum(p, i, j, k); if (start > all) all = start; } if (all > maxSum) maxSum = all; } } return maxSum; }
编程之美2.15 二维数组最大子数组的和(数组下标从(1,1)开始)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。