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 **