0

''How to determine the longest increasing subsequence using dynamic programming?'' didn't help me enough that I could do it on my own so I am asking for your help.

I have a sequence of integers: (-2, 4, 1, 1, 5, -2, 3, 3, -1, 1). I want to find longest sequence of them according to these requirements using dynamic programming (X here is a number, i its index):

  1. The numbers have to go in order, their indexes would keep increasing
  2. If the index is an odd number, this requirement has to be met: Xi <= Xi+1, if the index is an even number, this requirement has to be met: Xi >= Xi+1.

For example longest sequence would be: (-2, 4, 1, 5, -2, 3, -1, 1). Any help is greatly appreciated, I have been on this for the whole day..!

taudau1
  • 11
  • 3
  • If that in quotes is another question on SO, please link it for other readers, to whom it may be useful. _"I have been on this for the whole day"_ And what code did you come up with so far? SO is not a code-writing service; some evidence of prior effort is usually expected. – underscore_d Apr 20 '18 at 12:17
  • 1
    I am trying to think of a way to implement before mentioned code for my needs, but so far unsuccessfully, otherwise I would of posted what I have – taudau1 Apr 20 '18 at 12:34
  • Just how fast do you want the solution to be? An `O(n^2)` solution is rather straightforward, with `fun (index) = max length of sequence ending on this index`. Improving it to `O(n log n)` looks possible, using the same idea as the LIS solution you linked above, but with different requirements for even and odd positions. – Gassa Apr 20 '18 at 13:44
  • 1
    I managed to solved it on my own, thank You for the responses – taudau1 Apr 20 '18 at 15:34

0 Answers0