ZOJ-1074* 和值最大子矩阵
1074：给出一个N*N矩阵，求所有子矩阵中能达到的最大和值。
动态规划。矩阵是二维的，先降维，想象把矩阵压扁成一维数组。数组中每个值是原矩阵一列的和值。然后问题转化成和最大的连续子串问题。
求连续子串最大和值O(n)可解。从头扫描累和，遇负数和值则舍弃。因为负值成了接下来的负担。
求子矩阵要确定起始的行和终止的行。在相同起始行下，列和数组是增量计算的，避免了重复计算。
计算演示。 确定行范围，扩展列。 行向下扩展过程中列只需增量计算。
A B C A B C A B C A B C A B C
A B C A B C A B C A B C A B C
A B C A B C A B C A B C A B C
#include<stdio.h>#include<memory.h>#include<iostream>using namespace std;int matrix[100][100];int colsum[100];//计算连续字串最大和值，O(n)int findmaxsum(int *p,int N){int currsum=0;int maxsum=p[0];for(int i=0;i<N;i++){currsum+=p[i];if(currsum<0)currsum=0;else if(currsum>maxsum)maxsum=currsum;}return maxsum;}int main(){int N;cin>>N;for(int i=0;i<N;i++)for(int j=0;j<N;j++)cin>>matrix[i][j];int tmp;int max=matrix[0][0];//起始行for(int rs=0;rs<N;rs++){//初始化memset(colsum,0,100*sizeof(int));//终结行for(int re=rs;re<N;re++){//列值增加，求区域和for(int col=0;col<N;col++){colsum[col]+=matrix[re][col];tmp=findmaxsum(colsum,col+1);if(tmp>max)max=tmp;}}}cout<<max<<endl;}