POJ 1050 求最大子矩阵和动态规划

56 阅读 0 评论 37 点赞

我是靠谱客的博主甜美路人，这篇文章主要介绍POJ 1050 求最大子矩阵和动态规划，现在分享给大家，希望可以做个参考。

在王晓东算法书上有讲解，是最大子序列和问题的拓广

#include <iostream> using namespace std; int rec[102][102]; int b[100]; int main(){ int n,k,s,sum,max; int i,j; cin>>n; for (i = 0;i < n;i++) for (j = 0;j < n;j++) { cin>> rec[i][j]; } s = 0; for (i = 0;i < n;i++) { for (k = 0;k < n;k++) b[k] = 0; for (j = i;j < n;j++) { for (k = 0;k < n;k++) b[k]+=rec[j][k]; sum = 0; max = 0; for (k = 0;k < n;k++) { if (sum + b[k] > 0) sum+=b[k]; else sum = b[k]; if (sum > max) max = sum; } if (max > s) s = max; } } cout<<s<<endl; return 0; }