awdawdaw
查看原帖
awdawdaw
1726629
liu_rui_xuan329楼主2025/7/29 18:31
#include<bits/stdc++.h>
using namespace std;
int maxSubArray(vector<int>& nums) {
    int max_sum = INT_MIN;
    int current_sum = 0;
    for (int num : nums) {
        current_sum += num;
        if (current_sum > max_sum) {
            max_sum = current_sum;
        }
        if (current_sum < 0) {
            current_sum = 0;
        }
    }
    return max_sum;
}
int main() {
    int n;
    cin >> n;
    vector<vector<int>> grid(n, vector<int>(n));
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            cin >> grid[i][j];
        }
    }
    
    int max_sum = INT_MIN;
    vector<vector<int>> col_prefix(n + 1, vector<int>(n, 0));
    for (int j = 0; j < n; ++j) {
        for (int i = 1; i <= n; ++i) {
            col_prefix[i][j] = col_prefix[i - 1][j] + grid[i - 1][j];
        }
    }
    for (int i = 0; i < n; ++i) {
        for (int j = i; j < n; ++j) {
            vector<int> compressed_col(n);
            for (int k = 0; k < n; ++k) {
                compressed_col[k] = col_prefix[j + 1][k] - col_prefix[i][k];
            }
            int current_max = maxSubArray(compressed_col);
            if (current_max > max_sum) {
                max_sum = current_max;
            }
        }
    }
    
    cout << max_sum << endl;
    
    return 0;
}
2025/7/29 18:31
加载中...