lovro-sinda's blog

Easy task — DP

By lovro-sinda, 10 years ago, In English

We have a sequence. What is the smallest number should be removed to sequence be a growing array?

Example: 5 1 2 4 3 6 4 6

If left sequence 1 2 4 6 then we kicked four numbers.

And if you leave the series 1 2 3 4 6 then we threw three the number of which is better than four.

So answer is 3. Can anyone have any idea how to solve by DP? Sorry for bad English.

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
10 years ago, # |
  Vote: I like it +4 Vote: I do not like it

What you need to do is to find longest increasing subsequence. If its length is K and length of array is N then the answer is N - K.

Dynamic programming: dp[i] = the longest increasing subsequence ending in i-th element.

So dp[i] = {maximum for all j: 0 <= j < i and a[j] < a[i]} (dp[j] + 1)

So basically

int dp[N];
for (int i = 0; i < N; i++) {
   dp[i] = 1;
   for (int j = 0; j < i; j++) {
      if (a[j] < a[i]) dp[i] = max(dp[i], dp[j] + 1);
   }
}
int res = 0;
for (int i = 0; i < N; i++) res = max(res, dp[i]);
→ Reply
»
10 years ago, # |
  Vote: I like it +7 Vote: I do not like it

We can improve solution to O(NlogM), where M = length of LIS. Here it was discussed.

My code in C++

→ Reply