题解 | #最大子矩阵#

int fun(int* arr,int n);

int main(){
    int n = 0;
    scanf("%d",&n);
    int arr[n][n];
    int total[n][n];
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            //初始化辅助数组
            total[i][j] = 0;
        }
    }
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            scanf("%d",&arr[i][j]);
            //求辅助数组
            if(i == 0)
                total[i][j] = arr[i][j];
            else
                total[i][j] = total[i-1][j] + arr[i][j];
        }
    }
    
    //从一行到n行遍历
    int max = -999;
    int tmp = 0;
    int ass[n];
    for(int i = 0; i < n; i++){
        ass[i] = 0;
    }
    for(int i = 1; i <= n; i++){
        for(int j = i-1; j < n; j++){
            for(int k = 0; k < n; k++){
                if(j < i)
                    ass[k] = total[j][k];
                else
                    ass[k] = total[j][k] - total[j-i][k];
            }
            tmp = fun(ass,n);
            max = tmp > max ? tmp : max;
        }
    }
    printf("%d",max);
    return 0;
}

//一维数组求最大和
int fun(int* arr,int n){
    int max = 0;
    int prev = arr[0];
    max = prev;
    if(n == 1){
        return max;
    }
    for(int i = 1; i < n; i++){
        prev = (prev + arr[i]) > arr[i] ? (prev + arr[i]) : arr[i];
        max = max > prev ? max : prev;
    }
    return max;
}