试题详情
简答题给定一个由n个数组成的序列，要求该序列的最长单调上升子序列，请设计对应的算法并分析其时间复杂度，如果时间复杂度劣于O（nlogn）的，将其优化为O（nlogn）时间复杂度的算法。
  • 假设当前已求出m[1..i-1]，当前保留的状态集合为S，下面计算m[i]。
    1、若存在状态k∈S，使得x[k]=x[i]，则状态m[i]必定不需保留，不必计算。因为，不妨设m[i]=m[j]+1，则x[j] 2、否则，m[i]=1+max{m[j]|x[j] 3、若2成立，则我们往S中增加了一个状态，为了保持S的性质，我们要对S进行维护，若存在状态k∈S，使得m[i]=m[k]，则我们有x[i]x[i]，j∈S}。于是状态k应从S中删去。
    从性质D和算法描述可以发现，S实际上是以x值为关键字（也是以m值为关键字）的有序集合。若使用平衡树实现有序集合S，则该算法的时间复杂度为O（n*logn）。（每个状态转移的状态数仅为O（1），而每次状态转移的时间变为O（logn））。

  • 关注下方微信公众号，在线模考后查看

热门试题