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;
}