力扣-最长递增子序列

简单记录学习~

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。

子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

示例 1：

输入：nums = [10,9,2,5,3,7,101,18]
输出：4
解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。

示例 2：

输入：nums = [0,1,0,3,2,3]
输出：4

示例 3：

输入：nums = [7,7,7,7,7,7,7]
输出：1

这道题可以采用O(n^2)的动态规划解法和O(nlogn)的贪心+二分查找的解法

dp算法：

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int lengthOfLIS(vector<int>& nums) {
    int n = nums.size();
    if (n == 0) return 0;
    
    vector<int> dp(n, 1);  // 每个位置初始化为 1
    
    // 遍历每一个位置 i
    for (int i = 0; i < n; ++i) {
        // 遍历每一个比 i 小的位置 j
        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());  // 返回 dp 数组中的最大值
}

int main() {
    vector<int> nums = {10, 9, 2, 5, 3, 7, 101, 18};  // 示例输入
    cout << "Length of Longest Increasing Subsequence: " << lengthOfLIS(nums) << endl;
    return 0;
}

贪心＋二分查找：

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
    if (nums.empty()) return 0;
    
    vector<int> tails;  // 用来记录每个长度的递增子序列的末尾元素
    
    for (int num : nums) {
        // 二分查找：寻找 num 应该插入的位置
        auto it = lower_bound(tails.begin(), tails.end(), num);
        
        // 如果 num 小于等于 tails 中某个值，就替换掉它
        if (it != tails.end()) {
            *it = num; // 这一步严格保证了我们在计算的是递增子序列且是按照原数组的顺序得到的递增子序列
        } else {
            // 如果 num 大于 tails 中的所有值，添加到末尾
            tails.push_back(num);
        }
    }
    
    return tails.size();  // 最终的 tails 长度就是最长递增子序列的长度
}

};