网站建设建设意见,12306网站 给手机核验怎么做,德州建设银行兑换网站,网站开发文档步骤应该怎么写Maximum Sum 大意#xff1a;给你一个n*n的矩阵#xff0c;求最大的子矩阵的和是多少。 思路#xff1a;最開始我想的是预处理矩阵#xff0c;遍历子矩阵的端点#xff0c;发现复杂度是O(n^4)。就不知道该怎么办了。问了一下#xff0c;是压缩矩阵#xff0c;转换成最大… Maximum Sum 大意给你一个n*n的矩阵求最大的子矩阵的和是多少。 思路最開始我想的是预处理矩阵遍历子矩阵的端点发现复杂度是O(n^4)。就不知道该怎么办了。问了一下是压缩矩阵转换成最大字段和的问题。 压缩行或者列都是能够的。 int n, m, x, y, T, t;
int Map[1010][1010];int main()
{while(~scanf(%d, n)){memset(Map, 0, sizeof(Map));for(int i 1; i n; i){for(int j 1; j n; j){scanf(%d, t);Map[i][j] Map[i-1][j]t;}}int Max -INF;for(int i 1; i n; i){for(int j i; j n; j){int sum 0;for(int k 1; k n; k){sum sum0?0:sum; sum Map[j][k]-Map[i-1][k]; Max max(sum, Max); } } } printf(%d\n, Max); } return 0; }转载于:https://www.cnblogs.com/mengfanrong/p/5286839.html
