Блог пользователя lovro-sinda

Easy task — DP

Автор lovro-sinda, 11 лет назад, По-английски

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.

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
11 лет назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

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]);
→ Ответить
»
11 лет назад, # |
  Проголосовать: нравится +7 Проголосовать: не нравится

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

My code in C++

→ Ответить