描述

给定一个整数序列，找到最长上升子序列（LIS），返回LIS的长度。

说明

最长上升子序列的定义：

最长上升子序列问题是在一个无序的给定序列中找到一个尽可能长的由低到高排列的子序列，这种子序列不一定是连续的或者唯一的。
https://en.wikipedia.org/wiki/Longest_increasing_subsequence

样例

样例 1:
    输入:  [5,4,1,2,3]
    输出:  3

    解释:
    LIS 是 [1,2,3]

样例 2:
    输入: [4,2,4,5,3,7]
    输出:  4

    解释: 
    LIS 是 [2,4,5,7]

思路：

表示以结尾的最长上升子序列长度，则，具体实现如下。

class Solution {
public:
    /**
     * @param nums: An integer array
     * @return: The length of LIS (longest increasing subsequence)
     */
    int longestIncreasingSubsequence(vector<int> &nums) {
        // write your code here
        int n=nums.size();
        if(!n)
        {
            return 0;
        }
        vector<int> dp(n,0);
        int res=0;
        for(int i=0;i<n;i++)
        {
            dp[i]=1;
            for(int j=0;j<i;j++)
            {
                if(nums[i]>nums[j])
                {
                    dp[i]=max(dp[i],dp[j]+1);
                }
            }
            res=max(res,dp[i]);
        }
        return res;
    }
};