当前位置：首页 > news >正文

网站排名恢复印度疫情最新消息

news 2025/7/5 2:00:21

网站排名恢复,印度疫情最新消息,小程序制作步骤,企业微网站制作教程题目： 思路： 通常来说，子序列不要求连续，而子数组或子字符串必须连续；对于子序列问题，第一种动态规划方法是，定义 dp 数组，其中 dp[i] 表示以 i 结尾的子序列的性质。在处理好每个…

题目：
在这里插入图片描述

思路：

通常来说，子序列不要求连续，而子数组或子字符串必须连续；
对于子序列问题，第一种动态规划方法是，定义 dp 数组，其中 dp[i] 表示以 i 结尾的子序列的性质。在处理好每个位置后，统计一遍各个位置的结果即可得到题目要求的结果。
在本题中， dp[i] 可以表示为以 i 结尾的、最长子序列长度。对于每个位置 i ，如果其之前的某个位置 j 所对应的数字小于位置 i 所对应的数字，则我们可以获得一个以 i 结尾、长度为 dp[j] + 1 的子序列。为了遍历所有情况，我们需要对 i 和 j 进行两层循环，其时间复杂度为 O（n2）。

参考：
https://blog.csdn.net/weixin_43894455/article/details/130477427
https://blog.csdn.net/qfc_128220/article/details/127931755

代码：

public int lengthOfLIS(int[] nums) {//动态规划表int[] dp = new int[nums.length];// dp[0] = 1; // 这里不行，考虑为什么？int max = 1;for (int i = 0; i < nums.length; i++) {//base case 每个位置本身长度dp[i] = 1;for (int j = 0; j < i; j++) {// i 位置依次向前比 ,比j 位置大,就是 1 + dp[i]// 根据不同j位置上的数,来更新最大值if (nums[i] > nums[j]) {      // 注意，这里比较的是 nums ,不是dp数组dp[i] = Math.max(dp[i], 1 + dp[j]);max = Math.max(max, dp[i]);}}}return max;}