# longest increasing subsequence with at most k deletion

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.

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] 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$$.

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.
• Try to improve your answer by using math.meta.stackexchange.com/questions/5020/… – Valent Feb 25 at 3:50
• It is unclear what step 3 in this algorithm means. Furthermore, this version could only work if the OP intended that the 'offset' of the subarray is counted as deletions. – Steven Mar 7 at 11:18