Ta có thể xây một ma trận ~n \times n~, với ô ~(i,j)~ có giá trị bằng ~sum(i,j)~.

Lúc này, yêu cầu của bài toán cần chọn ra hai đoạn ~[x,y]~ và ~[c,d]~, chính là chọn ra một hình chữ nhật trong ma trận có chiều rộng từ ~x~ tới ~y~ và chiều dài từ ~c~ tới ~d~.

Như vậy, ta quy về bài toán tìm hình chữ nhật con có tổng lớn nhất.

Độ phức tạp: ~O(n^3)~.

Code mẫu

#include <bits/stdc++.h>
#define int long long
#define ii pair<int, int>
#define st first
#define nd second
#define endl "\n"
#define all(v) v.begin(), v.end()
#define Unique(v) v.erase(unique(all(v)), v.end())

using namespace std;

const int maxn = 405;
const int oo = 1e18;

int n, a[maxn], b[maxn];

int sum[maxn][maxn];



void PROGRAM(int _){
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= n; i++) cin >> b[i];


    for (int x = 1; x <= n; x++){
        for (int y = x; y <= n; y++){
            sum[x][y] = sum[x][y - 1] + a[y];
        }
    }

    for (int x = 1; x <= n; x++){
        for (int y = x - 1; y >= 1; y--){
            if (x - y > 1) sum[x][y] = sum[x][y + 1] + b[y];
            else sum[x][y] = b[y + 1] + b[y];
        }
    }

    for (int x = 1; x <= n; x++){
        for (int y = 1; y <= n; y++){
            sum[x][y] += sum[x][y - 1];
        }
    }

    auto getSum = [&] (int colL, int colR, int row){
        return sum[row][colR] - sum[row][colL - 1];
    };
    int ans = -oo;
    for (int colL = 1; colL <= n; colL++){
        for (int colR = colL; colR <= n; colR++){
            int Min = 0, sum = 0;
            for (int row = 1; row <= n; row++){
                int sumR = getSum(colL, colR, row);
                sum += sumR;
                ans = max(ans, sum - Min);
                Min = min(Min, sum);
            }
        }
    }
    cout << ans << endl;
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int test = 1;

    for (int _ = 1; _ <= test; _++){
        PROGRAM(_);
    }

    return 0;
}