参考最大子序列和前缀和 采用dp思路清晰易懂

解题思路:

注意事项:

参考代码:

import java.util.Arrays;

import java.util.Scanner;

public class Main {

    static int n;

    static int m;

public static void main(String[] args) {

Scanner sc = new Scanner(System.in);

n = sc.nextInt();

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();

}

}

//使用一个一维数组保存每一次上界和下界范围内的每一列的和 将多维矩阵压缩为一维数组

int[] sum = new int[m];

int max = arr[0][0];

//以每一行为上界

for (int i = 0; i < n; i++) {

Arrays.fill(sum, 0);//对于每次换上界时 sum数组归零

//确定下界

for (int j = i; j < n; j++) {

//遍历累加每一个元素

for (int k = 0; k < m; k++) {

sum[k] += arr[j][k];

}

//每当一次下界确定完成时

//参考最大子序列长度代码即可 dp数组每一位代表以当前下标结尾序列的最大和

int[] dp = new int[m];

dp[0] = sum[0];

for (int l = 1; l < dp.length; l++) {

dp[l] = Math.max(dp[l - 1] + sum[l], sum[l]);

if(dp[l] > max) {

max = dp[l];

}

}

}

}

System.out.println(max);

}

}