Minimum number of elements which are not part of Increasing or decreasing subsequence in array

Правка en1, от proCoderVP, 2024-01-24 10:01:36

Hello everyone, I wanted help in one question of dynamic programming. Given an array find the minimum number of elements which are not part of Increasing or Decreasing subsequence. For example

array = [7, 8, 1, 2, 4, 6, 3, 5, 2, 1, 8, 7]

optimally we can select, increasing = [1, 2, 4, 5, 8], decreasing = [7, 6, 3, 2, 1], only 2 elements are not part of any sequence, hence answer for this case is 2.

array = [1, 4, 2, 3, 3, 2, 4, 1]

optimally we can select, increasing = [1, 2, 3, 4], decreasing = [4, 3, 2, 1], no element remains, hence answer for this case is 0.

There is one solution available top down memoization solution. It is a 3D DP solution.

I was thinking to change the problem to find the maximum number of elements that can be part of increasing or decreasing subsequence and subtract it from total number of elements to get the answer. I was trying to form the recurrence relation but unable to do that. Can anyone help out to solve the problem using tabulation and explain? Thank you.

Теги dynamic programming, #3d-dp

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский proCoderVP 2024-01-24 10:01:36 1257 Initial revision (published)