Ural 1146. Maximum Sum
DP，最大子矩阵和：先按列压缩为一维i，如将每一列从左至右递加至一个一位数组，再用最大连续子序列和来求。
/*最大子矩阵和，先压缩为一维再求最大子序列和，时间复杂度O(n^3)*/#include
#include
#define N 1100
#define INF 0x3f3f3f3f
int a[N][N],s[N],n;void get_sum(int x ,int y)
{for(int i=0; imax?sum:max;if(sum<0) sum=0;}return max;
}
int main()
{while(scanf("%d",&n)!=EOF){for(int i=0; imax?ans:max;}printf("%d\n",max);}return 0;
} 本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！