longest increasing subsequence with at most k deletion

Question

Given a number array of length n and a number k, what is the longest non-decreasing contiguous subarray if we allow at most k deletions in our original array?

example: n, k = 5, 2 array = 5 2 1 3 4

answer = 2 3 4 with deleting 1 from index 2.

Answer 1

Suppose the initial array is named $R$. The problem can be solved by storing $k+1$ lists $L_i, 0\leq i \leq k$. Element $L_i[t]$ denotes the length of the longest non-decreasing subarray ending with (and using) element $t$ of $R$, with at most $i$ deletions. These lists can be filled in a dynamic-programming fashion. $L_i[0]=1$, for all $i$. Suppose all lists $L_i$ are filled up to index $t$. Then we can determine $L_i[t+1]$ for all $i$ by simple reasoning.

For example: if $R[t+1]<R[t]$ then $L_0[t+1]=1$ because we cannot append element $t+1$ to the subarray ending at element $t$. Otherwise, $L_0[t+1]=L_0[t]+1$.

For $L_1[t+1]$ we need to take the maximum of two possibilities: either we skip element $R[t]$ and end up with a subarray of length $L_0[t-1]+1$ (if $R[t-1]\leq R[t+1]$), or we allow an earlier skip and use $L_1[t]+1$ (if $R[t]\leq R[t+1]$).

Filling in $L_i[t+1]$ for $i>1$ is completely analogous, and requires to take the maximum over the lengths reached by the $i+1$ possible skips. The longest subarray with at most $k$ skips is then equal to the maximal value found in the list $L_k$.

Answer 2

You can use DP to solve this problem.

1. subproblem: $dp(i)$ = length of non-decreasing subsequence ending at index i
2. recurrence: $dp(j) = max_{i < j, A[i] <= A[j]} ${dp(i)}$ + 1$ where . This is because the subsequence ending at index j is going to be extended by some subsequence ending at a previous index of i. E.g. 1,2,3,...i,..j. So we maximum over all position ending before j s.t. $A[i] <= A[j]$. After we find it, we add 1 additional element, which is jth element.
3. To find the solution, we have to take $max_{0 <= j <= n}$ ${dp(j)}$ and the sum of 'decreasing' element should less than k. This is because j can be anywhere in the array and we also need to consider k.
4. The time complexity is $O(n^{2})$ because we have to solve n subproblem and each of them takes O(n) time.