题解 | #递减种子序列# java
递减种子序列
https://www.nowcoder.com/practice/708a3a8603274fc7b5732c5e73617203
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; // 初始化为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
知识点:动态规划
代码简短解释:使用一个数组 f
来记录每个位置的最长上升子序列长度,然后通过两层循环遍历数组,逐步更新 f
数组。最后,通过遍历 f
数组找到最大的长度值,即为最长上升子序列的长度。