top1编程
← 返回题目
题解

最大子阵和

1 条题解

  • 0
    @ 2026-7-29 0:22:08
    #include <iostream>
    #include <climits>
    using namespace std;
    
    const int MAXN = 100;
    
    int main() {
        int N;
        int matrix[MAXN][MAXN];
        int rowSum[MAXN];
        
        while (cin >> N) {
            for (int i = 0; i < N; ++i) {
                for (int j = 0; j < N; ++j) {
                    cin >> matrix[i][j];
                }
            }
    
            int maxSum = INT_MIN;
    
            // 枚举左右边界
            for (int left = 0; left < N; ++left) {
                for (int i = 0; i < N; ++i) {
                    rowSum[i] = 0;
                }
                
                for (int right = left; right < N; ++right) {
                    // 计算每一行在[left, right]列的和
                    for (int i = 0; i < N; ++i) {
                        rowSum[i] += matrix[i][right];
                    }
    
                    // 使用Kadane算法求最大子数组和
                    int currentSum = 0;
                    for (int i = 0; i < N; ++i) {
                        if (currentSum > 0) {
                            currentSum += rowSum[i];
                        } else {
                            currentSum = rowSum[i];
                        }
                        if (currentSum > maxSum) {
                            maxSum = currentSum;
                        }
                    }
                }
            }
    
            cout << maxSum << endl;
        }
        return 0;
    }
    
    • 1