网站建设管理视频,wordpress 离线编辑,好吊顶网站,雄安免费网站建设公司题目描述
给你一个整数数组 nums #xff0c;找到其中最长严格递增子序列的长度。
子序列 是由数组派生而来的序列#xff0c;删除#xff08;或不删除#xff09;数组中的元素而不改变其余元素的顺序。例如#xff0c;[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。
示…题目描述
给你一个整数数组 nums 找到其中最长严格递增子序列的长度。
子序列 是由数组派生而来的序列删除或不删除数组中的元素而不改变其余元素的顺序。例如[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。
示例 1
输入 nums [10,9,2,5,3,7,101,18] 输出 4 解释 最长递增子序列是 [2,3,7,101]因此长度为 4 。
示例 2
输入 nums [0,1,0,3,2,3] 输出 4
示例 3
输入 nums [7,7,7,7,7,7,7] 输出 1
提示
1 nums.length 2500-104 nums[i] 104
代码及注释
func lengthOfLIS(nums []int) int {// 创建一个动态规划数组 dp其中 dp[i] 表示以 nums[i] 结尾的最长上升子序列的长度dp : make([]int, len(nums))// 初始化结果为 1因为每个单独的元素本身就是一个长度为 1 的上升子序列res : 1// 初始化 dp 数组的第一个元素为 1dp[0] 1// 遍历整个数组for i : 1; i len(nums); i {// 初始化 dp[i] 为 1因为单个元素本身就是一个长度为 1 的上升子序列dp[i] 1// 遍历当前元素之前的所有元素for j : 0; j i; j {// 如果当前元素大于前面的某个元素且加入当前元素后能构成更长的上升子序列if nums[i] nums[j] {// 更新 dp[i]取当前的 dp[i] 和 dp[j] 1加入当前元素后的长度的较大值dp[i] max(dp[i], dp[j] 1)}}// 更新结果 res取当前的 res 和 dp[i] 的较大值res max(res, dp[i])}// 返回结果 res即最长的上升子序列的长度return res
}// 辅助函数返回两个整数中的较大值
func max(a, b int) int {if a b {return a}return b
}代码解释
动态规划数组 dp
在这个问题中我们使用动态规划来解决。我们定义了一个 dp 数组其中 dp[i] 表示以 nums[i] 结尾的最长上升子序列的长度。通过这种方式我们可以迭代地计算更长的上升子序列并找到最长的一个。
1.初始化
初始化 dp[0] 为 1因为单个元素本身就是一个长度为 1 的上升子序列。
2.状态转移 对于每个 nums[i]我们需要检查之前的所有元素 nums[j]j i。如果 nums[i] nums[j]则说明我们可以将 nums[i] 加入到以 nums[j] 结尾的子序列中从而构成一个更长的上升子序列。 因此我们更新 dp[i] max(dp[i], dp[j] 1)。
3.更新结果
每次更新 dp[i] 后我们都更新全局的最长上升子序列长度 res。
