Q108 - Maximum Sum

HSCHE

給你一個NxN的陣列，請你找出有最大和的子區域（sub-rectangle）其和為多少。一個區域的和指的是該區域中所有元素值的和。一個區域是指相連的任意大小的子陣列。例如，對以下的二維陣列：

其最大和的子區域位於左下角，並且其和為15。如下所示：

Input

只有一組測試資料，第一列有一個正整數N（N <= 100），代表此二維陣列大小為NxN。

從第二列起有N^2個整數，代表此陣列的內容。每個整數都介於-127到127之間，且以列為主（row-major）的順序排列。Sample Input即為上圖所示的陣列。

Output

輸出有最大和的子區域其和是多少。

Sample Input

40 -2 -7  0 9  2 -6  2-4  1 -4  1 -18  0 -2

Sample Output

15

在此附上題目連結UVA:http://uva.onlinejudge.org/external/1/108.htmlLUCKY CAT:http://luckycat.kshs.kh.edu.tw/homework/q108.htm
解題感想:這題主要是考二維陣列，使用的方法是先將二維壓縮成一維，再用一維去運算，只要能壓縮成功，這題就輕鬆ＧＧ

ＡＣ　ＣＯＤＥ：

#include<iostream>

#include<cstring>

#include<cstdio>

using namespace std;

int main()

{

        int a[101][101];

        long long int h,maxx=0,tot=0;

        cin>>h;

        for(int i=1;i<=h;i++)

        {

                for(int j=1;j<=h;j++)

                {

                        cin>>a[i][j];

                }

        }

        for(int i=1;i<=h;i++)

        {

                for(int j=2;j<=h;j++)

                {

                        a[i][j]+=a[i][j-1];

                }

        }

        for(int x=1;x<=h;x++)

        {

                for(int x2=x;x2<=h;x2++)

                {

                        //cout << "(" << x << "," << x2 << ")" << endl;

                        for(int i=1;i<=h;i++)

                        {

                                a[i][0]=0;

                                tot+=a[i][x2]-a[i][x-1];

                                

                                //cout << "total : " << tot << endl;

                                

                                if(tot>maxx)

                                {

                                        maxx=tot;

                                }

                                if(tot<=0)

                                tot=0;

                        }

                        tot=0;

                }

        }

        cout<<maxx<<"\n";

        return 0;

}