Can someone explain how do to get the array of

**LIS**, that is the**dp[]**array we normally get in**LIS**using**n^2 algo**. using**nlogn algo**. that is*patience sort*? Thanks.# | User | Rating |
---|---|---|

1 | tourist | 3629 |

2 | maroonrk | 3447 |

3 | Um_nik | 3441 |

4 | Benq | 3406 |

5 | ksun48 | 3395 |

6 | ecnerwala | 3380 |

7 | boboniu | 3300 |

8 | Petr | 3268 |

9 | ainta | 3246 |

10 | Radewoosh | 3245 |

# | User | Contrib. |
---|---|---|

1 | Errichto | 207 |

2 | Monogon | 197 |

3 | SecondThread | 191 |

4 | pikmike | 187 |

5 | antontrygubO_o | 186 |

6 | vovuh | 185 |

7 | Um_nik | 183 |

8 | Ashishgup | 182 |

9 | Radewoosh | 169 |

10 | pashka | 168 |

Can someone explain how do to get the array of **LIS **, that is the **dp[]** array we normally get in** LIS** using **n^2 algo**. using **nlogn algo**. that is *patience sort *? Thanks.

↑

↓

Codeforces (c) Copyright 2010-2020 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Oct/01/2020 10:41:21 (h1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

O(NlogN) timeI think I did not make it clear:

dp[i]is the array of LIS lengths starting atithelement.(starting means the first element of the LIS is

a[i])i] is the length of maximum increasing subsequence. And, of course, by increasingi, dp[i] also increases, so that dp[i] ≤ dp[i+ 1]. Because when length of arrayAincreases, probability of longer increasing subsequence also increases. So, when you are going to find dp[i], you can use binary search. Like this:http://ideone.com/tHksB

it stores the longest decreasing subsequences's length from backwards.

It can be modified to find LIS also i guess.

Your is itself a longest increasing sequence.

But My dp[] is actually , the " lengths " of LIS ,

your d[] and my vec are same thing.

But I wanted the dp[].

Thanks for trying to help, but my doubt is clear now.

Thanks again.