main.cpp

ACM题解： To The Max 一个应用动态规划的例子

#include <iostream>
#include <vector>

using namespace std;

int num[1000][1000];
int ar[1000];

int main()
{
    unsigned int n, i, j, k, m;
    int msum = 0;
    while(cin>>n) {
        msum = 0;
        for(i=0; i<n; i++) {
            for(j=0; j<n; j++) {
                cin>>num[i][j];
            }
        }
        for(i=0; i<n; i++) {
            for(j=i+1; j<n; j++) {
                for(k=0; k<n; k++) {
                    ar[k] = 0;
                    for(m=i; m<=j; m++) {
                        ar[k] += num[m][k];
                    }
                }
                int maxSum = 0;
                int sum = 0;
                vector<int> a(0),b(0);
                for (k=0; k<n; k++) {
                    sum += ar[k];
                    if (sum > maxSum ) {
                        for(m=0;m<b.size();m++) {
                            a.push_back(b[k]);
                        }
                        b.clear();
                        maxSum = sum;
                        a.push_back(ar[k]);
                    } else if (sum < 0) {
                        a.clear();
                        b.clear();
                        sum = 0;
                    } else {
                        b.push_back(ar[k]);
                    }
                }
                if(maxSum > msum) {
                    msum = maxSum;
                }
            }
        }
        cout<<msum<<endl;
    }
    return 0;
}