题解 | #递减种子序列#

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

与最长不下降子序列类似，这里dp【i】表示第i个位置之前有多少比seeds【i】大的数字，转移方程是取dp【i】与dp【j】+1的较大值，两层循环表示遍历所有i之前的数，判断是否大于第i个位置的数。每个i前面的数都遍历后更新一次最大长度。