最长上升子序列

int lengthOfLIS(vector<int>& nums) {
    int n = nums.size();
    if (n <= 1) return n;

    vector<int> dp(n, 1); // 需要关注初始值，以任何元素为起点，子序列长度至少为 1
    int ans = 0;
    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);
        }
        // 注意，答案要从 dp数组中找到最大值
        ans = max(ans, dp[i]);
    }
    return ans;
}