题解 | #递减种子序列#

题目考察的知识点：动态规划

题目解答方法的文字分析：用一个dp表表示以结尾的最大子序列的长度，以某一个位置为结尾进行分析；以i为结尾，那么如果i之前的数大于i（i之前的下标记为j），那么构成递减子序列，所以可以dp[i]=dp[j]+1，但是有很多个dp[j]+1，所以取最大的附给dp[i]。

本题解析所用的编程语言：c++

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param seeds int整型vector 
     * @return int整型
     */
    int lengthOfLIS(vector<int>& seeds) {
        // write code here
        int n = seeds.size();
        vector<int> dp(n, 1);
        int ret = 1;
        for (int i = 1; i < n; ++i)
        {
            for (int j = 0; j < i; ++j)
            {
                if (seeds[j] > seeds[i])
                    dp[i] = max(dp[j] + 1, dp[i]);
            }
            ret = max(dp[i], ret);
        }
        return ret;
    }
};