POJ1050 To the Max 简单动态规划

187 阅读 0 评论 124 点赞

我是靠谱客的博主寒冷芒果，这篇文章主要介绍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;
}