善变的同伴（快手校招题）

image.png
image.png

分析

这个题目实际上是M段最大子段和的变式
可以通过动态规划来做

dp[i][j]代表共取 i 次菜，当前取完第 j 个菜时，最大的好吃程度之和
所以d[i][j] 有两个选择

1. 选择以当前j为最后新开的一段的首，即与之前的段不连续，之前共有i-1段，则当前d[i][j] = Max(d[i-1][k])+A[j] k = i - j-1;
2. 当前j添加到最后一段的末尾
   d[i][j] = d[i][j-1] + A[j];

以上两种方法的结果取最大的那个

public class Cookie {


    public static int get(int[] A,int M){
        int N = A.length;
        int dp[][] = new int[2][N];
        //滚动数组
        //记录两行
        for(int i = 0; i < N;i++){
            dp[0][i] = 0;
            dp[1][i] = 0;
        }

        //算出M = 1的一行
        int nowMax = Integer.MIN_VALUE;
        for(int i = 0; i < N;i++) {
            if (nowMax < 0) {
                nowMax = A[i];
            } else {
                nowMax = nowMax + A[i];
            }
            dp[1][i] = nowMax;
        }

        // M > 1时，利用滚动数组减少存储空间
        for(int i = 2,k = 0; i <= M; i++,k^=1){
            int beforeLineMax = Integer.MIN_VALUE;
            dp[k][i-2] = Integer.MIN_VALUE;
            for(int j = i-1; j < i + N - M;j++){
                beforeLineMax = Integer.max(beforeLineMax,dp[k^1][j-1]);
                dp[k][j] = Integer.max(beforeLineMax,dp[k][j-1])+A[j];
            }
        }
        int res = Integer.MIN_VALUE;
        //得到当前第M行的最大值
        for(int i = M; i < N ;i++){
            res = Integer.max(res,dp[M&1][i]);
        }
        return res;
    }
    public static void main(String args[]){
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int M = sc.nextInt();
        int A[] = new int[N];
        for(int i = 0; i < N;i++){
            A[i] = sc.nextInt();//保存菜品
        }
        System.out.println(get(A,M));
    }
}

过程分析

备注（列号1对应下标为0）

	1	2	3	4	5	6	7
M=0	1	2	3	-2	3	-10	3
M=1	1	3	6	4	7	-3	3
M=2		3	6	4	9	-1	10

过程

image.png

d[i][j]相当于同一行的前一格子+当前格子或者前一行（i~j-1）+当前格子的最大值