最大子矩阵和，动态规划.txt

ACM资料大集合

#include <iostream>

using namespace std;
//求最大连续子矩阵和，动态规划，O(n^3) of time:
/*
输入
4
1 -4 3 -8
-3 5 2 -3
2 -1 8 1
-1 1 -2 -4

输出
14
*/

int max_sum(int n, int *arr)
{	//求单个序列的最大连续子串和
    int result=0;
	int b=0;
	for(int i=0;i<n;i++)
	{
		if(b>0) b+=arr[i];
		else b=arr[i];
		if(b>result) result=b;
	}
	return result;
}

int max_sum2(int m, int n, int **arr)
{
	int result=0;
	int *b=new int[n];
	for(int i=0;i<m;i++)
	{
		memset(b,0,sizeof(int)*n);
		for(int j=i;j<m;j++)
		{
			for(int k=0;k<n;k++)
			b[k]+=arr[j][k];//b[k]=arr[i][k]+arr[i+1][k]+...+arr[j][k]
			//从例子来说，当i=1,j=2时，有b[k]=arr[1][k]+arr[2][k],这时取到max
            int max=max_sum(n,b);
			if(max>result) result=max;
		}
	}
	delete b;
	return result;
}

int main()
{
    int N;
	cin>>N;
	int i,j;
	int **arr=new int*[N];
	for(i=0;i<N;i++)
	{
		arr[i]=new int[N];
		for(j=0;j<N;j++)
		cin>>arr[i][j];
    }               
	cout<<max_sum2(N,N,arr)<<endl;
	for(i=0;i<N;i++)
		delete arr[i];
	delete arr;
	return 0;
}