/*
 * @lc app=leetcode.cn id=300 lang=cpp
 *
 * [300] 最长递增子序列
 */

// @lc code=start
// // 动态规划
// class Solution {
// public:
//     int lengthOfLIS(vector<int>& nums) {
//         if (nums.size() == 1) return 1;
//         int n = nums.size();
//         vector<int> dp(n, 1);
//         for (int i = 0; i < n; i++) {
//             for (int j = 0; j < i; j++) {
//                 if (nums[j] < nums[i]) {
//                     dp[i] = max(dp[i], dp[j] + 1);
//                 }
//             }
//         }
//         return *max_element(dp.begin(), dp.end());
//     }
// };


//二分搜索
class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int length = 1, n = nums.size();
        vector<int> d(n + 1, 0);
        d[length] = nums[0];
        for (int i = 1; i < n; ++i) {
            if (nums[i] > d[length]) {
                d[++length] = nums[i];
            } else {
                int left = 1, right = length;
                int pos = 0;
                while (left <= right) {
                    int mid = left + (right - left) / 2;
                    if (d[mid] >= nums[i]) {
                        right = mid - 1;
                    } else {
                        pos = mid;
                        left = mid + 1;
                    }
                }
                d[pos + 1] = nums[i];
            }
        }
        return length;
    }
};
// @lc code=end