首页 > 代码库 > 【编程之美】2.15 子数组之和的最大值（二维）
【编程之美】2.15 子数组之和的最大值（二维）
思路，有了一维的思路，我们想办法把二维问题转化为一维的问题。
我们假定已经选中了行的范围是 a-c 那么把每一列中 a-c的元素加起来就变成了一个一维的问题。只需对行的范围遍历，再用一维的方法来解就可以了。
注意，也可以对列的范围遍历，行和列那个小就对哪个遍历。 复杂度为O(M * N * min(M, N))
#include <stdio.h>#include <stdlib.h>void getSumCol(int * a, int aColNum, int RowBegin, int RowEnd, int * SumColArray){ for(int j = 0; j < aColNum; j++) { SumColArray[j] = 0; for(int i = RowBegin; i <= RowEnd; i++) { SumColArray[j] += *(a + i * aColNum + j); } }}int getMax2DArraySum(int * a,const int aRowNum,const int aColNum){ int MaxSum = a[0]; int Sum = 0; int * SumColArray = (int *)calloc(aColNum, sizeof(a[0])); for(int i = 0; i < aRowNum; i++) { for(int k = i; k < aRowNum; k++) { getSumCol(a, aColNum, i, k, SumColArray); Sum = SumColArray[0]; for(int j = 1; j < aColNum; j++) { Sum = (Sum > 0) ? Sum + SumColArray[j] : SumColArray[j]; MaxSum = (Sum > MaxSum) ? Sum : MaxSum; } } } free(SumColArray); return MaxSum;}int main(){ int a[4][5] = { { 1, 2, 3, 4, 5}, {-3,-5, 3,-8, 0}, { 2, 3, 5, 6, 8}, { -3,1, 2, 3, 0} }; int max = getMax2DArraySum((int*)a, 4, 5); return 0;}
【编程之美】2.15 子数组之和的最大值（二维）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。