最长上升子序列LIS

问题描述：数组nums中求最长上升的子序列，序列中元素不要求连续

思路参考添加链接描述

解法一
动态规划。dp[i] 表示以i为结尾的最长上升的子序列
递推公式： dp[i] = { max(dp[i], dp[j] + 1) ; 0 <= j < i && nums[i] > nums[j] }

代码实现

 private static int longestLengthOfSubsquence(int[] a) {
        int max = 1;
        int[] curentLongest = new int[a.length];
        curentLongest[0] = 1;
        for (int i = 1; i < a.length; i++) {
            curentLongest[i] = 1;
            for (int j = 0; j < i; j++) {
                if (a[i] > a[j]) {
                    curentLongest[i] = Math.max(curentLongest[i], curentLongest[j] + 1);
                }
            }
            max = Math.max(max, curentLongest[i]);
        }
        return max;
    }

解法2: 贪心算法，维护一个单调递增的栈，当前元素比栈顶元素大直接插入，当前元素比栈顶元素小，则从栈顶开始向下，将栈中最后一个大于当前元素的元素替换为当前元素

class Solution { // 8 ms, faster than 91.61%
public:
    int lengthOfLIS(vector& nums) {
        vector sub;
        for (int x : nums) {
            if (sub.empty() || sub[sub.size() - 1] < x) {
                sub.push_back(x);
            } else {
                auto it = lower_bound(sub.begin(), sub.end(), x); // Find the index of the smallest number >= x
                *it = x; // Replace that number with x
            }
        }
        return sub.size();
    }
};