题解 | #递减种子序列#

您的关注、点赞、收藏就是我创作的动力，三连支持阿Q！

题目考察的知识点

动态规划

题目解答方法的文字分析

这道题要求我们找出最长的连续生长速度递减的种子序列。

我们可以使用动态规划来解决该问题。定义一个 dp 数组，其中 dp[i] 表示以第 i 个种子结尾的最长递减生长速度序列的长度。我们可以根据前一个状态推导出当前状态，具体推导公式如下：

1. 如果第 i 个种子的生长速度大于左边的种子生长速度，则 dp[i] = dp[i-1] + 1，表示当前种子可以接在前一个种子后面构成一个更长的递减序列。
2. 否则，dp[i] = 1，表示当前种子无法接在前一个种子后面构成递减序列，只能以自身为起始构成一个递减序列。

最后，我们只需要遍历 dp 数组，找到其中的最大值，即为最长的连续生长速度递减的种子序列的长度。

本题解析所用的编程语言

C++

完整且正确的编程代码

class Solution {
public:
    int lengthOfLIS(vector<int>& seeds) {
        int n = seeds.size();
        if (n == 0) {
            return 0;
        }

        vector<int> dp(n, 1); // dp数组，dp[i]表示以第i个种子结尾的最长递减生长速度序列的长度
        int maxLen = 1; // 最长的连续生长速度递减的种子序列的长度

        for (int i = 1; i < n; ++i) {
            if (seeds[i] < seeds[i - 1]) {
                dp[i] = dp[i - 1] + 1;
            }
            maxLen = max(maxLen, dp[i]);
        }

        return maxLen;
    }
};

您的关注、点赞、收藏就是我创作的动力，三连支持阿Q！