算法题---最长上升子序列

动态规划思路分析

使用一维数组表示，dp[i] 代表以下标为i结尾的子序列，其中上升的个数。

初始化

dp[i] = 1

转移方程： dp[i] = max(dp[i], dp[j] + 1) # 0 <= j <i

返回值

返回dp[size] 数组中元素最大的值

// 最长上升子序列
int longChirldNums(vector<int> &nums){
    int size = nums.size();
    vector<int> dp(size, 0);
    for(int i=0; i<size; i++){
        dp[i] = 1;
        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());
}