POJ 1050 To the Max - (DP)

题目链接：http://poj.org/problem?id=1050
复杂度 $O(N^3)$，选取两列，然后把他们之间的矩阵压缩成一条竖线，
求一维连续最大字段和。

#include <stdio.h> 
#include <vector> 
#include <algorithm>
using namespace std;//POJ 1050 To the Maxint matrix[101][101];
int sumrow[101][101];int main()
{int N;scanf("%d", &N);const int l = N * N;for (int i = 1; i <= N; i++)for (int j = 1; j <= N; j++){scanf("%d", &matrix[i][j]);sumrow[i][j] = sumrow[i][j - 1] + matrix[i][j];}int _max = 0x80000000;for (int start = 1; start <= N; start++)for (int end = start; end <= N; end++){vector<int> dp(N + 1), v(N + 1);for (int row = 1; row <= N; row++)v[row] = sumrow[row][end] - sumrow[row][start - 1];dp[1] = v[1];_max = max(dp[1], _max);for (int i = 2; i <= N; i++){if (dp[i - 1] > 0)dp[i] = v[i] + dp[i - 1];else dp[i] = v[i];_max = max(_max, dp[i]);}}printf("%d", _max);system("pause");return 0;
}