题解 | #递减种子序列# 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 背包问题 分治算法:归并排序、快速排序