筆記：【演算法新手村】[初階]筆記05 - 前綴和(二維)

題目翻譯

給你一個 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

解題思路

這題其實就是多測資的 UVA 108 - Maximum Sum，可以看之前這篇 UVA 108 - Maximum Sum 詳解，幾乎完全相同

程式碼實作 (C++)

#include <iostream>
#include <climits>

using namespace std;

int main() {
    int n;
    while (scanf("%d", &n) != EOF){

        int arr[101][101] = {0};
        int sum[101][101] = {0};

        int Min = 0;
        int Max = INT_MIN;

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                scanf("%d", &arr[i][j]);
                sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + arr[i][j];
            }
        }

        for(int r1 = 1 ; r1 <= n ; r1++){
            for(int c1 = 1 ;  c1 <= n ; c1++){
                for(int r2 = r1 ; r2 <= n ; r2++){
                    for(int c2 = c1 ; c2 <= n ; c2++){
                        int cur_sum = sum[r2][c2] - sum[r2][c1-1] - sum[r1-1][c2] + sum[r1-1][c1-1];
                        if(cur_sum > Max){
                            Max = cur_sum;
                        }
                    }
                }
            }
        }

        printf("%d\n",Max);
    }
    return 0;
}