题解 | #递减种子序列#

一、知识点：

动态规划、循环、遍历

二、文字分析：

定义一个长度为n的数组dp，其中dp[i]表示以第i个种子结尾的最长递减序列的长度。

初始状态：对于任意的i，dp[i]的初始值都为1，因为每个种子自身构成一个递减序列。

状态转移方程：对于种子i，遍历种子j，其中j < i。如果seeds[j] > seeds[i]，说明种子j的生长速度比种子i慢，则可以将种子j加入到以种子i结尾的递减序列中，从而得到更长的递减序列。因此，dp[i] = max(dp[i], dp[j] + 1)。

最终结果为dp数组中的最大值。

时间复杂度：

• 双重循环遍历所有的种子对，时间复杂度为O(n^2)。
• 计算dp数组的过程需要遍历每个种子，时间复杂度为O(n)。
• 在更新dp数组的过程中，比较每个种子与之前的种子的生长速度，时间复杂度为O(n)。

因此，算法的总体时间复杂度为O(n^2)。

空间复杂度：

• 需要一个长度为n的dp数组来保存每个种子结尾的最长递减序列的长度，空间复杂度为O(n)。

所以，算法的总体空间复杂度为O(n)。

三、编程语言：

java

四、正确代码：

import java.util.*;


public class Solution {
    public int lengthOfLIS(int[] seeds) {
        int n = seeds.length;
        if (n == 0) return 0;

        int[] dp = new int[n];
        Arrays.fill(dp, 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] = Math.max(dp[i], dp[j] + 1);
                }
            }
            maxLength = Math.max(maxLength, dp[i]);
        }

        return maxLength;
    }
}