题解 | #递减种子序列# Java
递减种子序列
https://www.nowcoder.com/practice/708a3a8603274fc7b5732c5e73617203
这个问题可以使用动态规划来解决。我们可以定义一个数组 dp，其中 dp[i] 表示以第 i 个种子结尾的最长递减子序列的长度。然后我们可以遍历每一个种子，对于每一个种子，我们再遍历它之前的所有种子，如果之前的种子的生长速度比当前种子慢，那么我们就更新 dp[i] 的值。最后，我们遍历一遍 dp 数组，找到最大的值就是答案。
import java.util.*;
public class Solution {
public int lengthOfLIS (int[] seeds) {
int n = seeds.length;
int[] dp = new int[n];
Arrays.fill(dp, 1);
int ans = 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[j] + 1, dp[i]);
}
}
ans = Math.max(dp[i], ans);
}
return ans;
}
}
算法题刷刷刷 文章被收录于专栏
数组、链表、栈、队列、堆、树、图等。 查找和排序：二分查找、线性查找、快速排序、归并排序、堆排序等。 动态规划：背包问题、最长公共子序列、最短路径 贪心算法：活动选择、霍夫曼编码 图：深度优先搜索、广度优先搜索、拓扑排序、最短路径算法（如 Dijkstra、Floyd-Warshall） 字符串操作：KMP 算法、正则表达式匹配 回溯算法：八皇后问题、0-1 背包问题 分治算法：归并排序、快速排序
投递CVTE等公司7个岗位 >
查看6道真题和解析