Terror.java

import java.util.Scanner;

public class Terror {
    public static void main(String[] args) {
        /*
        Example input with 30 trains
30
11 15 16 17 24 31 42 44 45 54 57 77 79 90 92 96 102 104 110 120 123 129 131 134 150 151 153 178 192 193
         */
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int[] costs = new int[N - 1];
        int current = sc.nextInt();
        for (int i = 0; i < N - 1; i++) {
            int next = sc.nextInt();
            costs[i] = next - current;
            current = next;
        }

        int[][] dp = new int[N - 1][2]; // dp[n][i] : total cost for first n edges, if edge is taken/not (i = 1/0)
        dp[0][0] = costs[0];
        dp[0][1] = costs[0];

        for (int i = 1; i < N - 1; i++) {
            dp[i][0] = dp[i - 1][1];
            dp[i][1] = Math.min(dp[i - 1][0], dp[i - 1][1]) + costs[i];
        }

        boolean[] pick = new boolean[N - 1]; // bool for if edge is in min edge cover
        pick[dp.length - 1] = true;
        pick[0] = true;

        // trace back from last edge
        for (int i = dp.length - 2; i > 0; i--) {
            pick[i] = !pick[i + 1] || dp[i][1] < dp[i][0];
        }

        int max = 0;
        char[] direction = new char[N];
        for (int i = 0; i < pick.length; i++) {
            if (pick[i] && costs[i] > max) max = costs[i];

            if (pick[i]) {
                direction[i] = direction[i] == '◄' ? '▼' : '►';
                direction[i + 1] = '◄';
            }
        }

        System.out.println(max);
        System.out.println(direction);
    }
}