lot of platforms don't explain how this algorithm work they just say how you implement it but in PS you must understand more then you keep so I will explain that here -the basic idea of this algorithm is that if I have a sequence **{ 1 4 2 3 }** so at first I have **{ 1 }** as a sequence then I will have **{ 1 , 4 }** as a sequence then I will have **{ 1 , 4 , 2 }** but it is invalid cause it isn't sorted so what is the optimal action I can take here I will delete 4 and continue with a sequence **{ 1, 2}** because **2** has better chance than **4** to have a bigger number for example if I meet **3** I couldn't take it because **3<4** but if I took two at first I could take 3 easily so here is the idea: ***we minimize the last number as much as we can to increase the chance of taking more numbers *** so if I ask U what is the optimal solution you take for the sub-sequence of length 1 obviously its 1 because I can take more numbers after it more than any number else lets get back to the array *{1 , 4 , 2 , 3}*

I will make another array which carry the last number of the sequence of length i so I have the first subsequence {1} then the last number of a sequences of length 1 is 1 so I will put the value of the 1-th number of the array I made equal to 1 {1} then I have {1 , 4} so obviously the last number of sequence of length 2 is 4 {1 , 4} then i have {1 , 4 , 2} and it is invalid so now i will ask my self a question where can i put this two so it is instead of 4 so now the best option for the sub-sequences of length 2 isn't 4 but 2 so i will change it to {1 , 2} and then i will have 3 and i can put it in the back of sub-sequence of length 2 and then it will be 3 thus the **LIS({1,4,2,3}) = 3 **