题目描述

给定一个无序的整数数组，找到其中最长上升子序列的长度。

示例

输入: [10,9,2,5,3,7,101,18]
输出: 4
解释: 最长的上升子序列是 [2,3,7,101]，它的长度是 4。

说明:

• 可能会有多种最长上升子序列的组合，你只需要输出对应的长度即可。
• 你算法的时间复杂度应该为 O(n2) 。

思路

使用动态规划来解题，定义$d(i), (i \in [1,n])$ 表示前$i$个数以$A[i]$结尾的最长上升子序列的长度，而$d(i)=max\{d(1),d(2),……,d(i)\}$

于是从i=0开始，往后迭代序列，求得以i结尾的最大上升子序列，代码如下：

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        if (nums.size()==0) {
            return 0;
        }
        int n = nums.size();
        //定义d(i) (i∈[1,n])来表示前i个数以A[i]结尾的最长上升子序列长度
        int dp[n] = {0};
        int maxSeq = 0;
        for (int i = 0; i < n; i++) {
            maxSeq = 0;
            for (int j = 0; j <= i;j++) {
                if (nums[j] < nums[i]) {
                    maxSeq = max(dp[j], maxSeq);
                }
            }
            dp[i] = maxSeq + 1;
        }
        for (int i = 0; i < n; i++) {
            maxSeq = maxSeq > dp[i] ? maxSeq : dp[i];
        }
        return maxSeq;
    }
};