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.
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.Sign up to join this community
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=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$.
You can use DP to solve this problem.