Problem statement:

Given a number sequence, find the minimum number of elements that should be deleted to make the remaining sequence sorted.

Example:

Input: {4,2,3,6,10,1,12}
Output: 2
Explanation: We need to delete {4,1} to make the remaing sequence sorted {2,3,6,10,12}.

Input: {-4,10,3,7,15}
Output: 1
Explanation: We need to delete {10} to make the remaing sequence sorted {-4,3,7,15}.

Solution

length of input array - longest increasing subsequence

Longest Increasing Subsequence

public int minDeletionsBU(int[] arr) {
    return arr.length - findLIS(arr);
}

int findLIS(int[] arr) {
    int[] dp = new int[arr.length];
    Arrays.fill(dp, 1);
    int max = 0;
    for (int i = 1; i < arr.length; i++) {
        for (int j = 0; j < i; j++) {
            if (arr[i] > arr[j] && dp[i] <= dp[j]) {
                dp[i] = 1 + dp[j];
            }
        }
        max = Math.max(dp[i], max);
    }
    return max;
}

Or two steps recursion
public int minDeletions(int[] arr) {
    Map<String, Integer> dp = new HashMap<>();
    return minDeletionsRec(arr, 0, -1, dp);
}

int minDeletionsRec(int[] arr, int curr, int prev, Map<String, Integer> dp) {
    if (curr >= arr.length) return 0;
    String key = prev + "_" + curr;
    if (!dp.containsKey(key)) {
        int min1 = Integer.MAX_VALUE;
        if (prev == -1 || arr[curr] > arr[prev]) {
            min1 = minDeletionsRec(arr, curr + 1, curr, dp);
        }
        int min2 = 1 + minDeletionsRec(arr, curr + 1, prev, dp);
        dp.put(key, Math.min(min1, min2));
    }
    return dp.get(key);
}

Time complexity:

O(N^2)

Space complexity:

O(N)

Approach:

length of input array - longest increasing subsequence