✅  ❌ {{ user_message.number_answer }}

Longest Increasing Subsequence iterative solution.

Try to solve the problem by yourself before looking at the solution. You can chat with the Bot 🤖. He'll build your intuition step by step without giving you a straight answer.

1. Given array of numbers

For example [2,3,2,4,5]

2. Initialize array of LIS for every element

By default LIS to current element is 1

3. Build array of previous positions

That's position from which current LIS was incremented. By default it's -1 (from no position)

4. Start searching from every position values less than current

We're looking for the less values with the maximum LIS. For now there is only element with value 2 ans LIS 1.

5. Use found element's LIS

Increment it by 1 and save as current element's LIS.

6. Save position from which LIS was continued

We'll need it for reconstructing the global LIS path.

7. Move to the next element 2

Start searching for the less elements with max LIS again. There is no elements less than 2. Leave current element's LIS and PREV unchanged.

8. Move to the next element 4

Start searching for the less elements with max LIS again. That is the element with value 3 and LIS 2.

9. Update the LIS and the PREV position.

As we've done it before.

10. Update LIS and prev for the last element with value 5

LIS becomes 4 from the previous element from position 3

11. Find the max LIS and return it

For the example array the max LIS is 4

12. If you asked to return the LIS elements just follow PREV positions.

Follow them until PREV doesn't equal to -1. Don't forget to reverse the result, because you've been following positions in the reverse order. 5,4,3,2 => 2,3,4,5

Start Chat