## {{ current_question_unmet_requirement.title }} {{ user_message.course_message.title }} Admin Delete

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