题解 | #递减种子序列#

知识点：

LIS问题，动态规划

分析：

状态表示：

1.f[i]表示以第i个数字结尾的子序列的最长的递减种子序列

2.属性：max，最长

状态计算：

1.分为两个部分

1.1一个部分是，包含seeds[i]这个数字的，那么以这个结尾的最长的递减子序列长度，抛开这个即将要计算的seeds[i]数字来说，其最长长度为f[j]+1，其中j取的是0~i，表示取一个最长的之前计算的最长递减长度，再加1

1.2另一个部分是不包含seeds[i]的，那么就是以上一个包含了seeds[i]的数字结尾的长度，也就是之前计算的f[i]

综上，f[i] = max(f[i],f[j]+1)

编程语言：

C++

完整代码：

    int f[2510];
    int lengthOfLIS(vector<int>& seeds) {
        int res = 0;
        f[0] = 1;
        for(int i = 0;i<seeds.size();i++){
            f[i] = 1;
            for(int j = 0;j<i;j++){
                if(seeds[i] <seeds[j]){
                    f[i] = max(f[i],f[j] + 1);
                }          
            }
            res = max(res,f[i]);
        }
        return res;
    }