POJ1050解题报告

原题：思路：动态规划 + 贪心
其实这道题目就是一维数组求连续数和最大的一个扩展版，而现在的任务就是要把这个二维数组的问题归结为几个一维
数组求连续数和最大的子问题，而这些子问题可以用贪心法解决。

设每一行有N个数，那么用state[i][j]记录i <= n <= j的连续数的和，那么每一行总共有N（N+1)/2种状态。把所有行垒起来，
也就是说一共有N（N+1）/2个一维数组的子问题（按列的方向看）。

思路其实就这么简单。
代码：

#include <iostream>
#include <cstring>

using namespace std;

#define N 100

int state[N][N];
int array[N][N];
int _max;
int size;

bool init() {
    _max = -127;
    for (int i=0; i<size; i++)
        for (int j=0; j<size; j++) {
            cin >> array[i][j];
            if (array[i][j] > _max)
                _max = array[i][j];
        }
    if (_max < 0)
        return true;
    else
        _max = 0;
    return false;
}

void dp() {
    for (int n=0; n<size; n++) {
        for (int i=0; i<size; i++) {
            int sum = 0;
            for (int j=i; j<size; j++) {
                sum += array[n][j];
                state[i][j] += sum;
                if (state[i][j] > _max)
                    _max = state[i][j];
                if (state[i][j] < 0)
                    state[i][j] = 0;
            }
        }
    }
}

int main() {
    while (cin >> size) {
        if (!init())
            dp();
        cout << _max << endl;
    }
    return 0;
}