uva-108-贪心

题意：

求二维数组中子数组中的最大和.

使用二维数组,第i行表示前i行的和.那么a[i-j]表示从j行到i行的和.注意第三层循环,每次都保存当前最大的sum，如果sum小于0，直接置0.

#include"pch.h"
#include <string>
#include<iostream>
#include<map>
#include<memory.h>
#include<vector>
#include<algorithm>
#include<queue>
#include<vector>
#include<stack>
#include<math.h>
#include<iomanip>
#include<bitset>
#include"math.h"
namespace cc
{
    using std::cout;
    using std::endl;
    using std::cin;
    using std::map;
    using std::vector;
    using std::string;
    using std::sort;
    using std::priority_queue;
    using std::greater;
    using std::vector;
    using std::swap;
    using std::stack;
    using std::queue;
    using std::bitset;


    constexpr int N = 200;

    int a[N][N];
    void solve()
    {
        memset(a, 0, sizeof(a));
        int nn;
        cin >> nn;
        for (int i = 1;i <= nn;i++)
        {
            for (int j = 1;j <= nn;j++)
            {
                int cur = 0;
                cin >> cur;
                a[i][j] = a[i - 1][j] + cur;
            }
        }
        int ans = INT32_MIN;

        for (int i = 0;i <= nn;i++)
        {
            for (int j = i;j <= nn;j++)
            {
                int sum = 0;
                for (int col = 1;col <= nn;col++)
                {
                    //当前行的最大值
                    if (i == j)
                    {
                        if (sum < 0)
                            sum = a[i][col];
                        else
                            sum += a[i][col];
                    }
                    else
                    {
                        if (sum < 0)
                            sum = a[j][col] - a[i][col];
                        else
                            sum += a[j][col] - a[i][col];
                    }
                    if (sum > ans && sum != 0)
                        ans = sum;
                }
            }

        }
        cout << ans << endl;


    }
};


int main()
{

#ifndef ONLINE_JUDGE
    freopen("d://1.text", "r", stdin);
#endif // !ONLINE_JUDGE
    cc::solve();

    return 0;
}