思路很难想,纯纯的背诵题 #include<iostream> #include<vector> #include<limits> #include<algorithm> using namespace std; #define N 105 long long matrix[N][N]; long long total[N][N]; //用于辅助计算 long long dp[N]; long long arr[N]; long long Maxlength(int n) { long long maximal = -1000000; for (int i = 0; i < n; i++) { if (i == 0) dp[i] = arr[i]; else { dp[i] = max(dp[i - 1] + arr[i], arr[i]); } maximal = max(maximal, dp[i]); } return maximal; } long long Maxsubmatrix(int n) { long long maximal = -1000000; for (int i = 0; i < n; i++) { // 每k列中前i到j行的所有和中求最大值 for (int j = i; j < n; j++){ for (int k = 0; k < n; k++) { if (i == 0) { arr[k] = total[j][k]; } else arr[k] = total[j][k] - total[i - 1][k]; } long long temp = Maxlength(n); maximal = max(temp, maximal); } } return maximal; } int main() { int n; while (cin >> n) { for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { cin >> matrix[i][j]; } } // 计算辅助数组total (初始化操作) for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (i == 0) total[i][j] = matrix[i][j]; else { total[i][j] = total[i - 1][j] + matrix[i][j]; } } } long long res = Maxsubmatrix(n); cout << res << endl; } }