//经典DP 线性DP

//dp[i]    那么 nums[i] 必然要大于 nums[j]，才能将 nums[i] 放在nums[j] 后面以形成更长的上升子序列。

func lengthOfLIS(nums []int) int {

    if len(nums) <= 1{

        return len(nums)

    }

    var res int

    dp := make([]int,len(nums))

    dp[0] = 1

    //d[0] = nums[0]

    for i:=1;i<len(nums);i++{

        m := 0

        for j:=i-1;j>=0;j--{

            if dp[j] > m && nums[j]<nums[i]{

                m = dp[j]

            }

        }

        dp[i] = m+1

        res = MAX(dp[i],res)

        //d[i] = nums[i]

    }

    return res

}

func MAX(i,j int) int{

    if i<j{

        return j

    }else{

        return i

    }

}

class Solution {

public:

    //最长递增子序列

    int lengthOfLIS(vector<int>& nums) {

        vector<int> res;

        for(int i=0;i<nums.size();i++){

            if(res.size() ==0 || nums[i] > res.back()){

                res.push_back(nums[i]);

                continue;

            }

            int left=0,right=res.size()-1;

            while(left<=right){

                //找第一个大于等于nums[i]的数，在之前插入

                int mid=left+(right-left)/2;

                if(nums[i]<= res[mid]) right = mid-1;

                else left=mid+1;

            }

            res[left] = nums[i];

        }

        return res.size();

    }

};