优化后就过了, 下面有未优化代码

import java.io.*;
class Main{
    static BufferedReader read = new BufferedReader(new InputStreamReader(System.in));
    public static void main(String[] args) throws Exception{
        int N = 100010, K = 110, INF = 0x3f3f3f3f;
        String[] ss = read.readLine().split(" ");
        int[] a = new int[N];
        int[][] dp = new int[K][2];
        int n = Integer.valueOf(ss[0]);
        int k = Integer.valueOf(ss[1]);
        ss = read.readLine().split(" ");
        for(int i = 1; i <= n; i++){
            a[i] = Integer.valueOf(ss[i - 1]);
        }
        for(int j = 0; j <= k; j++){
            dp[j][0] = -INF;
            dp[j][1] = -INF;
        }

        dp[0][0] = 0;
        for(int i = 1; i <= n; i++){
            for(int j = k; j >= 1; j--){
                dp[j][0] = Math.max(dp[j][0], dp[j][1]+a[i]);
                dp[j][1] = Math.max(dp[j][1], dp[j-1][0]-a[i]);
            }
        }
        int max = 0;
        for(int i = 0; i <= k; i++) max = Math.max(max, dp[i][0]);
        System.out.println(max);
    }
}

TLE

import java.io.*;
class Main{
    static BufferedReader read = new BufferedReader(new InputStreamReader(System.in));
    public static void main(String[] args) throws Exception{
        int N = 100010, K = 110, INF = 0x3f3f3f3f;
        String[] ss = read.readLine().split(" ");
        int[] a = new int[N];
        int[][][] dp = new int[N][K][2];
        int n = Integer.valueOf(ss[0]);
        int k = Integer.valueOf(ss[1]);
        ss = read.readLine().split(" ");
        for(int i = 1; i <= n; i++){
            a[i] = Integer.valueOf(ss[i - 1]);
        }
        for(int i = 0; i < N; i++){
            for(int j = 0; j < K; j++){
                dp[i][j][0] = -INF;
                dp[i][j][1] = -INF;
            }
        }
        for(int i = 0; i <= n; i++) dp[i][0][0] = 0;
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= k; j++){
                dp[i][j][0] = Math.max(dp[i-1][j][0], dp[i-1][j][1]+a[i]);
                dp[i][j][1] = Math.max(dp[i-1][j][1], dp[i-1][j-1][0]-a[i]);
            }
        }
        int max = 0;
        for(int i = 0; i <= k; i++) max = Math.max(max, dp[n][i][0]);
        System.out.println(max);
    }
}