ac(类子数组最大累加和)

import java.util.Scanner;


public class Main {

    public static Scanner sc = new Scanner(System.in);

    public static void main(String[] args) {
        int n = sc.nextInt();
        int m = sc.nextInt();
        int[][] arr = new int[n][m];
        for(int i = 0; i < n; i ++){
            for(int j=0;j<m;j++) {
                arr[i][j] = sc.nextInt();
            }
        }
        // 构造每一列的累加和，方便得到每一列某两行之间的和
        // sums[i] - sums[j] 表示 (j+1, i] 行的sums
        // 0 1 2 ... n
        int[][] sums = new int[n+1][m];
        for(int i=0;i<m;i++){
            sums[0][i] = 0;
        }
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                sums[i+1][j] = sums[i][j] + arr[i][j];
            }
        }
        int ans = 0;
        // 哪两行构成的矩形,降成一维来处理
        for(int i=0;i<n;i++){
            for(int j=i;j<n;j++){
                int[] vals = new int[m];
                // 判断最大累加和问题
                for(int k=0;k<m;k++){
                    vals[k] = sums[j+1][k] - sums[i][k];
                }
                // O(m) 判断 最长递增序列
                ans = Math.max(getMaxLen(vals, m), ans);
            }
        }
        System.out.println(ans);
    }

    static int getMaxLen(int[] arr, int n) {
        int[] dp = new int[n];
        dp[0] = arr[0];
        int ans = dp[0];
        for(int i=1;i<n;i++){
            dp[i] = Math.max(dp[i-1] + arr[i], arr[i]);
            if(dp[i] > ans){
                ans = dp[i];
            }
        }
        return ans;
    }

}
/*
3 3
-90 48 78
64 -40 64
-81 -7 66

209


3 3
-1 -1 -1
-1 2 2
-1 -1 -1

4
*/