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.
For example [2,3,2,4,5]
By default LIS to current element is 1
That's position from which current LIS was incremented. By default it's -1 (from no position)
We're looking for the less values with the maximum LIS. For now there is only element with value 2 ans LIS 1.
Increment it by 1 and save as current element's LIS.
We'll need it for reconstructing the global LIS path.
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.
Start searching for the less elements with max LIS again. That is the element with value 3 and LIS 2.
As we've done it before.
LIS becomes 4 from the previous element from position 3
For the example array the max LIS is 4
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