Java 题解 | #递减种子序列#

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param seeds int整型一维数组
     * @return int整型
     */
    public int lengthOfLIS (int[] seeds) {
        // write code here
        int n = seeds.length;
        int[] f = new int[n];

        for (int i = 0; i < n; i++) {
            f[i] = 1;
            for (int j = 0; j < i; j++) {
                if (seeds[i] < seeds[j])
                    f[i] = Math.max(f[i], f[j] + 1);
            }
        }

        int res = 0;
        for (int i = 0; i < n; i++)
            res = Math.max(res, f[i]);
        return res;
    }
}

编程语言是Java。

该题考察的知识点是动态规划。

这段代码实现了一个函数 lengthOfLIS，它接受一个整型一维数组 seeds 作为输入，并返回一个整数。

使用动态规划来解决最长递增子序列（Longest Increasing Subsequence）问题。首先定义一个长度为 n 的辅助数组 f，其中 f[i] 表示以 seeds[i] 结尾的最长递增子序列的长度。

通过两层循环遍历数组 seeds。对于每个元素 seeds[i]，将 f[i] 初始化为1，并且在之前的所有元素 seeds[j]（其中 j 小于 i）中寻找比当前元素小的元素，如果找到则更新 f[i] 的值为 f[j] + 1。这样，在遍历完整个数组之后，数组 f 中的最大值即为最长递增子序列的长度。

返回 f 数组中的最大值作为结果。