善变的同伴

import java.util.Scanner;
//只能通过80%😂 public class Main{
    public static void main(String[] args){
        Scanner input = new Scanner(System.in);
        while(input.hasNext()) {
            int N = input.nextInt();
            int M = input.nextInt();
            int[] rank = new int[N];
            for(int i = 0; i < N; i++) {
               rank[i] = input.nextInt();
            }
            System.out.println(Solution(N, M, rank));
        }
        input.close();    
    }
     
    public static int Solution(int N, int M, int[] rank){
        int[] dp = new int[N+1];
        int[] pre_max = new int[N];
        for(int i = 1; i < M + 1; i++){
            for(int j = 1; j < N + 1; j++){
                dp[j] = rank[j-1] + ((dp[j-1] > pre_max[j-1]) ? dp[j-1] : pre_max[j-1]);
                if(j > 1) pre_max[j-1] = (pre_max[j-2] > dp[j-1]) ? pre_max[j-2] : dp[j-1];
            }
        }
        int max = dp[0];
        for(int i = 0; i < N + 1; i++) {
        	if(dp[i] > max) {
        		max = dp[i];
        	}
        }
        return max;
    }
}

import java.util.Scanner;
public class Main{
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        int N=sc.nextInt(),M=sc.nextInt();
        int[] A=new int[N];
        for(int i=0;i<N;i++){
            A[i]=sc.nextInt();
        }
        int[][] dp=new int[M+1][N+1];
        for(int i=1;i<=M;i++){
            int max=0;
            for(int j=i;j<=N;j++){
                //这里用max来表示dp[i-1][t]的最大值
                max=Math.max(max,dp[i-1][j-1]);
                dp[i][j]=Math.max(dp[i][j-1],max)+A[j-1];
            }
        }
        int ans=0;
        for(int i=1;i<=N;i++){
            ans=Math.max(ans,dp[M][i]);
        }
        System.out.println(ans);
    }
}