最长不下降子序列
题目链接:
题目:
求最长不下降子序列的长度
第一行为n,表示n个数 第二行n个数
最长不下降子序列的长度
N小于5000 for each num < =maxint
样例输入
31 2 3
样例输出
3 思路:可以用O(n*n)做,就刚学贪心+二分nlogn的做法,所以这里就试了一下nlogn做法,即采用lower_bound,维护单调数组, 对于序列 a(1, 7, 3, 5, 9, 4, 8),dp的变化过程如下:
- dp[0] = a[0] = 1,长度为1的LIS结尾元素的最小值自然没得挑,就是第一个数。 (dp = {1})
- 对于a[1]=7,a[1]>dp[0],因此直接添加到dp尾,dp[1]=a[1]。(dp = {1, 7})
- 对于a[2]=3,dp[0]< a[2]< dp[1],因此a[2]替换dp[1],令dp[1]=a[2],因为长度为2的LIS,结尾元素自然是3好过于7,因为越小这样有利于后续添加新元素。 (dp = {1, 3})
- 对于a[3]=5,a[3]>dp[1],因此直接添加到dp尾,dp[2]=a[3]。 (dp = {1, 3, 5})
- 对于a[4]=9,a[4]>dp[2],因此同样直接添加到dp尾,dp[3]=a[9]。 (dp = {1, 3, 5, 9})
- 对于a[5]=4,dp[1]< a[5]< dp[2],因此a[5]替换值为5的dp[2],因此长度为3的LIS,结尾元素为4会比5好,越小越好嘛。(dp = {1, 3, 4, 9})
- 对于a[6]=8,dp[2]< a[6]< dp[3],同理a[6]替换值为9的dp[3],道理你懂。 (dp = {1, 3, 4, 8})
这样子dp数组就维护完毕,所求LIS长度就是dp数组长度4。 AC代码如下:
//// Created by hanyu on 2019/8/9.//#include#include #include #include #include #include #include #include