题解 | #递减种子序列#

class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param seeds int整型vector
     * @return int整型
     */

    int lengthOfLIS(vector<int>& seeds) {
        // write code here
        int n = seeds.size();
        int dp[n];
        for (int i = 0; i < n; ++i)
            dp[i] = 1;
        int ans = 1;
        for (int i = 1; i < n; ++i) {
            for (int j = 0; j < i; ++j) {
                if (seeds[j] > seeds[i])
                    dp[i] = max(dp[i], dp[j] + 1);
            }
            ans = max(ans, dp[i]);
        }
        return ans;
    }
};

一、题目考察的知识点

二、题目解答方法的文字分析

最长递增子序的模板题

我们往后遍历，每次遍历的同时，我们在当前数a[i]前面寻找比它小的数但又是小的数里面b[i]最大的数，找到了那我们便在以当前数结尾的LIS加一，同时更新ans的值。循环结束的时候，ans就是我们要求的值

最长递增子序列的可能有很多，但我们只要找到一条即可当前的算法时间复杂度为O(n^2);

缺点就是复杂度过大O（n^2）

可以用二分优化成n*log（n）

三、本题解析所用的编程语言

c++