从动态规划到贪心算法：最长递增子序列问题的方法全解析

#include <iostream>
#include <vector>
 
using namespace std;
 
int lengthOfLIS(vector<int>& nums) 
{
    // 如果输入序列为空，返回 0
    if (nums.empty()) 
    {
        return 0;
    }
 
    // 定义 dp 数组，长度为输入序列的长度
    int dp[nums.size()];
    // 初始化 dp 数组，将所有元素初始化为 1
    for (int i = 0; i < nums.size(); i++) 
    {
        dp[i] = 1;
    }
 
    // 记录最长递增子序列的长度
    int maxn = 1;
 
    // 遍历输入序列，从第 2 个元素开始,因为第一个元素的 dp[0] 一定是 1
    for (int i = 1; i < nums.size(); i++) 
    {
        // 遍历之前的元素，找到满足条件的索引 j
        for (int j = 0; j < i; j++) 
        {
            // 如果当前元素小于之前的元素，并且之前元素的最长递增子序列长度加 1 大于当前元素的最长递增子序列长度
            if ((nums[j] < nums[i]) && (dp[j] + 1 > dp[i])) 
            {
                // 更新当前元素的最长递增子序列长度为之前元素的最长递增子序列长度加 1
                // 因为if条件是nums[j] < nums[i]，所以当前i位置的num一定是可以往j位置的数字后拼接作为递增子序列的
                // 所以更新当前i的dp作为新的当前dp[i]
                dp[i] = dp[j] + 1;
            }
        }
 
        // 在与每次遍历完当前i的j后更新的dp[i]与之前的maxn作对比
        // 得到当前最长递增子序列的长度
        if (dp[i] > maxn) 
        {
            maxn = dp[i];
        }
    }
 
    // 返回最长递增子序列的长度
    return maxn;
}
 
int main() 
{
    vector<int> nums = { 10, 9, 2, 5, 3, 7, 101, 18 };
    // 输出：4
    cout << lengthOfLIS(nums) << endl;
 
    return 0;
}

    for (int i = 1; i < nums.size(); i++) 
    {
        for (int j = 0; j < i; j++) 
        {
            if ((nums[j] < nums[i]) && (dp[j] + 1 > dp[i])) 
            {
                dp[i] = dp[j] + 1;
            }
        }
 
        if (dp[i] > maxn) 
        {
            maxn = dp[i];
        }
    }