dp状态机

import java.io.*;
class Main{

    static BufferedReader read = new BufferedReader(new InputStreamReader(System.in));
    static int N = 100010, INF = 0x3f3f3f3f;
    static int[][] dp = new int[N][2];
    public static void main(String[] args) throws Exception{
        String[] ss = read.readLine().split(" ");
        int n = Integer.valueOf(ss[0]);
        int f = Integer.valueOf(ss[1]);
        int[] a = new int[n + 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++){
            dp[i][1] = -INF;
        }

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

}