d206: 00108 - Maximum Sum

CPE 一顆星(騙人的吧)

題目連結:https://zerojudge.tw/ShowProblem?problemid=d206

內容

給你一個 N*N 的陣列，請你找出有最大和的子區域 (sub-rectangle)其和為多少。一個區域的和指的是該區域中所有元素值的和。一個區域是指相連的任意大小的子陣列。範例：
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 <= 100)，接著有 N*N 個數字代表此陣列，EOF結束。
輸入很醜，但是C/C++沒差。

範例輸入

4
0 -2 -7 0 9 2
-6 2 -4
1 -4 1 -1 8 0
-2 10 9 116 24 -121 30 14 2 119 122 28 -53 125 -71 87 -57 42 -111 125
-33 91 -121 30 -28 1 -16 97 -11 68 -24 103 -126 98 -61 33 48 109
-88 67 -72 77 -107 95 -78 23 -86 45 -4 28 -121 73 -57 20 -122 9
68 -97 79 -68 122 -42 88 -22 0 -116 55 -44 68 -109 43 -32 103 -54
122 -41 62 -114 113 -32 29 -22 99 -11 38 -60 88 -83 28 -83 122 -56
100 -86 63 -49 111 -77 91 -88 69 -110

範例輸出

15
963

想法

把陣列分成 N*j 來看(j為1~N)
像是4*4陣列
0 -2 -7 0
9 2 -6 2
-4 1 -4 1
-1 8 0 -2
將其拆成
4*1

0
9
-4
-1

-2
2
1
8

-7
-6
-4
0

0
2
1
-2

4*2

0 -2
9 2
-4 1
-1 8

-2 -7
2 -6
1 -4
8 0

-7 0
-6 2
-4 1
0 -2

4*3，4*4 同上方法。

並合併成一維數列
像是
-7 0
-6 2
-4 1
0 -2
變成
-7
-4
-3
-2
之後分別計算這些子陣列的最大連續子序列(一數列的最大區間和)，最大值即為所求。

為了方便操作，若輸入為
0 -2 -7 0
9 2 -6 2
-4 1 -4 1
-1 8 0 -2
可以將其儲存成
0 0 0 0 0
0 0 -2 -9 -9
0 9 11 5 7
0 -4 -3 -7 -6
0 -1 7 7 5
那麼

1
2

for(int i = 0; i < 4; ++i)
    for(int j = i+1; j <= 4; ++j)

把 i, j 當行來看(直的)，就可以將上面所有的一維數列都考慮進去，裡面再加一個迴圈進行最大連續子序列運算即可。

程式碼

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(false), cin.tie(nullptr)
using namespace std;

int main(){
    fastio;
    int N, dp[105][105];
    while(cin >> N){
        memset(dp, 0, sizeof(0));
        for(int i = 1; i <= N; ++i){
            for(int j = 1; j <= N; ++j){
                cin >> dp[i][j];
                dp[i][j] += dp[i][j-1];
            }
        }
        int mxn = INT_MIN, count;
        for(int i = 0; i < N; ++i){
            for(int j = i+1; j <= N; ++j){
                count = 0;
                for(int k = 1; k <= N; ++k){
                    count = max(count+dp[k][j]-dp[k][i], dp[k][j]-dp[k][i]);
                    mxn = max(mxn, count);
                    if(count < 0) count = 0;
                }
            }
        }
        cout << mxn << "\n";
    }
    return 0;
}

參考資料:inversion大神的小屋