题解
最大子阵和
1 条题解
-
0
#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