Sequence

Problem

Sequence

Approach

Let’s define dp[i][j], which means the smallest steps to make the subarray from 0 to i non-decreasing and the non-decreasing subarray is ended with j.

Then, if we use the elements’ range as the dimension, there will be overflow. So we can use the index of the original array.

Then, dp[i][j] = Max(dp[i - 1][k] + arr[j] - arr[k]), 0 <= k <= j, arr[j] >= arr[k]

Code

import java.util.*;
 
public class Main{
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        int N = in.nextInt();
        long[] arr = new long[N];
        Set<Long> set = new HashSet<>();
        for(int i = 0; i < N; i ++){
            arr[i] = in.nextInt();
            set.add(arr[i]);
        }
        List<Long> targets = new ArrayList<>(set);
        Collections.sort(targets);
        
        long[][] dp = new long[2][targets.size()];
        for(int i = 0; i < targets.size(); i ++){
            if(i == 0){
                dp[0][0] = Math.abs(targets.get(0) - arr[0]);
            } else {
                dp[0][i] = Math.min(dp[0][i - 1], Math.abs(targets.get(i) - arr[0]));
            }
        }
        for(int i = 1; i < N; i ++){
            dp[1][0] = dp[0][0] + Math.abs(arr[i] - targets.get(0));
            for(int j = 1; j < targets.size(); j ++){
                dp[1][j] = Math.min(dp[1][j - 1], dp[0][j] + Math.abs(arr[i] - targets.get(j)));
            }
            dp[0] = dp[1];
        }
        System.out.println(dp[0][targets.size() - 1]);
    }
}