POJ1050 To the Max 简单动态规划

POJ1050 To the Max

Description
给出N*N的矩阵，求它子矩阵的最大和。（将求最大子矩阵转换为求最大子段和的问题）

Sample Input
4
0 -2 -7 0 9 2 -6 2
-4 1 -4 1 -1

8 0 -2

Sample Output
15

题解：
整理ing

AC_Code(cpp)：

#include<iostream>
using namespace std;
int Matrix[105][105];
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 sum, max = 0, h = 0;
for (int i = h; i < n; i++)
{
sum = 0;
for (int k = 0; k < n; k++)
{
for (int j = h; j <= i; j++)
{
sum += Matrix[j][k];
}
if (sum>max)
{
max = sum;
}
if (sum < 0)
sum = 0;
}
if (h != n - 2 && i==n-1)
{
h++;
i = h;
}
}
cout << max << endl;
return 0;
}

最后

以上就是寒冷芒果为你收集整理的POJ1050 To the Max 简单动态规划的全部内容，希望文章能够帮你解决POJ1050 To the Max 简单动态规划所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。