注意使用了辅助矩阵减少计算。
#include <iostream> #include <cstring> using namespace std; const int N = 100; int dp[N]; int total[N][N]; //辅助数组 int num[N][N]; //原始数组 int arr[N]; //一维数组 int getMaxSentence(int n){ int ans = arr[0]; dp[0] = arr[0]; for(int i = 1; i < n; i++){ dp[i] = max(arr[i], dp[i-1] + arr[i]); ans = max(ans, dp[i]); } return ans; } int getMaxMatrix(int n){ //long long ans = 0; 这里ans不能设为0,因为存在负数值 int ans = num[0][0]; for(int i = 0; i < n; i++){ 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]; } } int current = getMaxSentence(n); ans = max(ans, current); } } return ans; } int main(){ int n; while(cin >> n){ for(int i = 0; i < n; i++){ for(int j = 0; j < n; j++){ cin >> num[i][j]; } } //初始化辅助矩阵 for(int i = 0; i < n; i++){ for(int j = 0; j < n; j++){ if(i == 0){ total[i][j] = num[i][j]; }else{ total[i][j] = total[i-1][j] + num[i][j]; } } } int ans = getMaxMatrix(n); printf("%d\n", ans); } return 0; }