保研機試刷題——2018年南大機試第一題，最大子矩陣和

題目是這樣的：

已知矩陣的大小定義為矩陣中所有元素的和。給定一個矩陣，你的任務是找到最大的非空(大小至少是1 * 1)子矩陣。

比如，如下4 * 4的矩陣

0 -2 -7 0

9 2 -6 2

-4 1 -4 1

-1 8 0 -2

的最大子矩陣是

9 2

-4 1

-1 8

這個子矩陣的大小是15。

輸入

輸入是一個N * N的矩陣。輸入的第一行給出N (0 < N <= 100)。

再後面的若幹行中，依次（首先從左到右給出第一行的N個整數，再從左到右給出第二行的N個整數……）給出矩陣中的N2個整數，整數之間由空白字元分隔（空格或者空行）。

已知矩陣中整數的範圍都在[-127, 127]。

輸出

測試資料可能有多組，對于每組測試資料，輸出最大子矩陣的大小。

樣例輸入

1
27 
3
-40 29 -16 
38 18 22 
24 -35 5 
      

樣例輸出

27
78      

其實吧，這題不難，主要就是要能轉過來一個彎：

将二維數組轉化為一維數組，然後通過該一維數組來找到最大連續子序列。

比如最大的連續子矩陣的和為從第 i 行 到 第 j 行的元素在列的方向上相加，得到一個一維數組arrtemp[]，然後計算出這個一維數組的最大子序列的和maxtemp，通過對 i 和 j 進行枚舉（1<=i<=N, i<=j<=N），計算出N(N-1)/2 個 maxtemp，取其中最大的那個作為最終的最大子矩陣的值。

/*
    實際上就是最大連續子序列和的問題，隻不過要對從i行到j行的所有的可能都枚舉
    然後要設定一個Max值來進行儲存并更新目前的最大值
*/
#include<iostream>
#include<cstring>
using namespace std;

int N;
int a[505][505];
int temp[505];

int max_oneVec(int an[])            //一維數組的動态規劃
{
    int dp2[505];
    dp2[1]=an[1];                   //邊界條件，第1個結尾的子串隻能是自己
    int maxnum=dp2[1];              //标記最大值
    for(int i=2;i<=N;i++)           //從第2個開始
    {
        if(dp2[i-1]>0)
        {
            dp2[i] = dp2[i-1]+an[i];
        }else
        {
            dp2[i] = an[i];
        }
        if(dp2[i]>maxnum)
        {
            maxnum = dp2[i];        //更新最大值
        }
    }
    return maxnum;
}

int main()
{
    cin>>N;
    for(int i=1;i<=N;i++)
    {
        for(int j=1;j<=N;j++)
        {
            cin>>a[i][j];
        }
    }
    int maxres=0;
    for(int i=1;i<=N;i++)   //從第一行開始搜尋
    {
        memset(temp,0,sizeof(temp));        //重置目前的dp數組
        for(int j=i;j<=N;j++)
        {
            for(int k=1;k<=N;k++)           //累加目前的從第i行到j行的數組值放入一維數組中
            {
                temp[k] += a[j][k];
            }
        }
        int maxtemp = max_oneVec(temp);     //該一維數組的最大值即為目前從i行到j行矩陣的最大值

        if(maxtemp>maxres)
        {
            maxres = maxtemp;
        }
    }
    cout<<maxres<<endl;
    return 0;
}