-010's blog

By -010, history, 2 months ago, In English

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

  • Vote: I like it
  • 0
  • Vote: I do not like it