最大子矩阵和代码问题-动态规划

Question

如题，最大子矩阵和问题，问题描述可参见POJ： http://poj.org/problem?id=1050

我想提问的具体问题是压缩子矩阵为一行的循环起点和循环终点，我自己写的完整代码如下：
int main(int argc, const char * argv[]) {
// insert code here...
// 最大子矩阵和问题
// first get all the numbers from the user
cout<<"Please first enter the dimension of this array as in N, then enter each one of the numbers in this array, with'enter's in between:";
int N;
cin>>N;
int a[N][N];
for (int i=1; i<=N; i++) {
for (int j=1; j<=N; j++) {
cin>>a[i][j];
}
}
int SofArray=0;
// for rectangles that have 1,2,3...,N rows, do the addition for each column
for (int i=1; i<=N; i++) {
//create the target row
int targetRow[N];
for (int j=1; j<=N; j++) {
targetRow[j]=0;
for (int k=1; k<=i; k++) {
targetRow[j]+=a[k][j];
}
}

//now do the 最大子段和 solution
int S=0,b=0;
for (int j=1; j<=N; j++) {
if (b<0) {
b=targetRow[j];
}
else {
b+=targetRow[j];
}
if (b>=S) {
S=b;
}
}
// compare S and SofArray
if (S>=SofArray) {
SofArray=S;
}
}
// give back the info to the user
cout<<"The max sum of sub-rectangles of this array is:"<<SofArray<<endl;

return 0;
}

（我是小白请勿嫌弃。。QAQ捂脸）

有一个地方跟标准答案不一样。。。就是压缩成一行那里（正文第22行）。。。我是for (int k=1;k<=i;k++)，就是k从1到i嘛，因为这里有i行j列呀。。。可是标准答案是for (int k=i;k<=N;k++),也就是k是从i到N了。。。就想知道这是为啥。。。先谢过！乃们都是大好人！！QAQ

Answer 1

参见http://www.cnblogs.com/tianshuai11/archive/2012/04/23/2477161.html，比较清楚
以链接中所说为例，形式(ar1+……+ak1, ar2+……+ak2, ……,arn+……+akn)表示第r行到第k行的n列子矩阵的和
而此数组的最大子段和即为所求。枚举所有[r,k]行,对每一种情况下求最大字段和，而[r,k] 和 [k,r]是一样的不需要重复计算，以三行为例，所有可能并不重复的情况为[1,1],[1,2],[1,3], [2,2], [2,3], [3,3]，所以代码中为从i到N，你的代码应该还要修改下。