经典DP做法(TLE)

//初始条件的设置，即将所有非法入口设置成无穷大
import java.util.*;
class Main{
    private static int inf = 0x3f3f3f3f;
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int[][][] f = new int[n+1][m+1][2];
        for(int j = 1; j <= m; j++){
            f[0][j][0] = -inf;
            f[0][j][1] = -inf;
        }
        for(int i = 1; i <= n; i++){
            int w = sc.nextInt();
            for(int j = 1; j <= m; j++){
                f[i][j][0] = Math.max(f[i-1][j][0], f[i-1][j][1] + w);
                f[i][j][1] = Math.max(f[i-1][j][1], f[i-1][j-1][0] - w);
            }
        }
        int res = 0;
        for(int j = 0; j <= m; j++) res = Math.max(res, f[n][j][0]);
        System.out.println(res);
    }
}

状态压缩一维可AC

import java.util.*;
class Main{
    private static int inf = 0x3f3f3f3f;
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int[][] f = new int[m+1][2];
        for(int j = 1; j <= m; j++){
            f[j][0] = -inf;
            f[j][1] = -inf;
        }
        for(int i = 1; i <= n; i++){
            int w = sc.nextInt();
            for(int j = m; j >= 1; j--){
                f[j][0] = Math.max(f[j][0], f[j][1] + w);
                f[j][1] = Math.max(f[j][1], f[j-1][0] - w);
            }
        }
        int res = 0;
        for(int j = 0; j <= m; j++) res = Math.max(res, f[j][0]);
        System.out.println(res);
    }
}