AcWing 896. 最长上升子序列 II【贪心】【二分】

AcWing 896. 最长上升子序列 II

• 
  

  一、题目链接

• 
  

  二、题目分析

• • （一）算法标签
  • （二）解题思路
• 
  

  三、AC代码

• 
  

  四、其它题解

---

一、题目链接

AcWing 896. 最长上升子序列 II

---

二、题目分析 （一）算法标签

贪心 二分

（二）解题思路

---

三、AC代码

解法一(O(nlogn)):

#include 
#include 
#include 

using namespace std;

const int N = 100010;

int a[N], q[N];
int n;

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i ++ ) scanf("%d", &a[i]);
    int len = 0;
    for (int i = 1; i <= n; i ++ )
    {
        int l = 0, r = len;
        while (l < r)
        {
            int mid = l + r + 1>> 1;
            if (q[mid] < a[i]) l = mid;
            else r = mid - 1;
        }
        q[l + 1] = a[i];
        len = max(len, l + 1);
    }
    cout << len << endl;
    return 0;
}

---

四、其它题解

AcWing 896. 最长上升子序列 II