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

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

See http://www.cnblogs.com/tianshuai11/archive/2012/04/23/2477161.html for more clarity
Taking what is mentioned in the link as an example, the form (ar1+…+ak1, ar2+…+ak2,…,arn+…+akn) represents the sum of the n-column submatrices from row r to row k
The maximum subsegment sum of this array is what is sought. Enumerate all [r,k] rows and find the maximum field sum in each case. [r,k] and [k,r] are the same and do not require repeated calculations. Take three rows as an example. All may not be The repeated cases are [1,1],[1,2],[1,3], [2,2], [2,3], [3,3], so from i to N in the code, you The code should still be modified.