题解 | #递减种子序列#

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param seeds int整型一维数组
     * @return int整型
     */
    public int lengthOfLIS (int[] seeds) {
        // write code here
        int n = seeds.length;
        int[] dp = new
        int[n]; // 用于记录以每个种子为结尾的最长递减序列的长度

        // 初始情况，每个种子都至少可以形成长度为 1 的递减序列
        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[i] < seeds[j]) {
                    dp[i] = Math.max(dp[i], dp[j] +
                                     1); // 更新以当前种子结尾的最长递减序列长度
                }
            }
            maxLength = Math.max(maxLength, dp[i]); // 更新最长递减序列的长度
        }

        return maxLength;
    }
}

知识点：

1. 动态规划：一种通过将问题分解成子问题，并存储子问题的解来解决问题的方法。
2. 最长递减子序列问题：在给定序列中，找到一个递减的子序列，使其长度最长。

解题思路：

使用了一个动态规划数组 dp 来记录以每个种子为结尾的最长递减序列的长度。通过迭代填充这个数组，我们可以计算出最长递减序列的长度。最终，我们返回最长递减序列的长度。

总之，这个问题涉及到了动态规划的应用，以及对最长递减子序列问题的求解方法。