0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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.
$\endgroup$
2
  • $\begingroup$ Try to improve your answer by using math.meta.stackexchange.com/questions/5020/… $\endgroup$ – Valent Feb 25 at 3:50
  • $\begingroup$ 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. $\endgroup$ – Steven Mar 7 at 11:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.