阿里云网站建设方案书,wordpress百度云影视,做外贸 用国内空间做网站,汕尾营销网站建设300.最长递增子序列
力扣题目链接(opens new window)
给你一个整数数组 nums #xff0c;找到其中最长严格递增子序列的长度。
子序列是由数组派生而来的序列#xff0c;删除#xff08;或不删除#xff09;数组中的元素而不改变其余元素的顺序。例如#xff0c;[3,6,2…300.最长递增子序列
力扣题目链接(opens new window)
给你一个整数数组 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 。
子序列问题分析
dp[i]的定义
dp[i]表示i之前包括i的以nums[i]结尾的最长递增子序列的长度
为什么一定表示 “以nums[i]结尾的最长递增子序” 因为我们在 做 递增比较的时候如果比较 nums[j] 和 nums[i] 的大小那么两个递增子序列一定分别以nums[j]为结尾 和 nums[i]为结尾 要不然这个比较就没有意义了不是尾部元素的比较那么 如何算递增呢。
状态转移方程
位置i的最长升序子序列等于j从0到i-1各个位置的最长升序子序列 1 的最大值。
所以if (nums[i] nums[j]) dp[i] max(dp[i], dp[j] 1);
注意这里不是要dp[i] 与 dp[j] 1进行比较而是我们要取dp[j] 1的最大值。
dp[i]的初始化
每一个i对应的dp[i]即最长递增子序列起始大小至少都是1.
确定遍历顺序
dp[i] 是有0到i-1各个位置的最长递增子序列 推导而来那么遍历i一定是从前向后遍历。
j其实就是遍历0到i-1那么是从前到后还是从后到前遍历都无所谓只要吧 0 到 i-1 的元素都遍历了就行了。 所以默认习惯 从前向后遍历。
注意**概括来说不连续递增子序列的跟前0-i 个状态有关连续递增的子序列只跟前一个状态有关——这也是考虑如何构建动态规划算法的方法
时间复杂度: O(n^2)空间复杂度: O(n)
int lengthOfLIS(int* nums, int numsSize) {int dp[numsSize];dp[0]1;int max_ans1;//结果不一定在最后一个位置for (int i1;inumsSize;i){dp[i]1;//为什么要初始化成1包含自己必然是最大的子序列尤其是涉及到fmax不能随便初始化的for (int j0;ji;j){if(nums[j]nums[i]) dp[i]fmax(dp[i],dp[j]1);}printf(%d,dp[i]);max_ansfmax(max_ans, dp[i]);}return max_ans;
} 674. 最长连续递增序列
力扣题目链接(opens new window)
给定一个未经排序的整数数组找到最长且 连续递增的子序列并返回该序列的长度。
连续递增的子序列 可以由两个下标 l 和 rl r确定如果对于每个 l i r都有 nums[i] nums[i 1] 那么子序列 [nums[l], nums[l 1], ..., nums[r - 1], nums[r]] 就是连续递增子序列。
示例 1
输入nums [1,3,5,4,7]输出3解释最长连续递增序列是 [1,3,5], 长度为3。尽管 [1,3,5,7] 也是升序的子序列, 但它不是连续的因为 5 和 7 在原数组里被 4 隔开。
示例 2
输入nums [2,2,2,2,2]输出1解释最长连续递增序列是 [2], 长度为1。 可以不用动态规划直接做贪心 on o1复杂度
int findLengthOfLCIS(int* nums, int numsSize) {int max_ans1;int this1;for (int i1;inumsSize;i){if(nums[i]nums[i-1]) {this;max_ansfmax(this, max_ans);} else {this1;}}return max_ans;
}
感觉动规做法过于复杂
int findLengthOfLCIS(int* nums, int numsSize) {int max_ans1;int dp[numsSize];dp[0]1;for (int i1;inumsSize;i){dp[i]1;if(nums[i]nums[i-1]) dp[i]dp[i-1]1;max_ansfmax(max_ans, dp[i]);}return max_ans;
} 718. 最长重复子数组
力扣题目链接(opens new window)
给两个整数数组 A 和 B 返回两个数组中公共的、长度最长的子数组的长度。
示例
输入
A: [1,2,3,2,1]B: [3,2,1,4,7]输出3解释长度最长的公共子数组是 [3, 2, 1] 。
提示
1 len(A), len(B) 10000 A[i], B[i] 100 分析
dp【i】【j】是以i位置、j位置为结尾的匹配的情况——所以只和左上位置元素相关
之前考虑的时候考虑成i位置、j位置以前的匹配的最大值情况发现没有办法从上一个状态推导到这个状态——优先直接出结果如果不能出结果可以退而求其次最大值的任务落在max_ans
上优先考虑本次状态的情况
int findLength(int* nums1, int nums1Size, int* nums2, int nums2Size) {int dp[nums1Size][nums2Size];memset(dp,0, sizeof(dp));if(nums1[0]nums2[0]) dp[0][0]1;int max_ans0;for (int i1;inums1Size;i){if(nums2[0]nums1[i]) dp[i][0]1;max_ansfmax(max_ans, dp[i][0]);}for (int j1;jnums2Size;j){if(nums1[0]nums2[j]) dp[0][j]1;max_ansfmax(max_ans, dp[0][j]);}for (int i1;inums1Size;i){for (int j1;jnums2Size;j){if(nums1[i]nums2[j]) dp[i][j]dp[i-1][j-1]1;max_ansfmax(max_ans, dp[i][j]);}}return max_ans;}
文章转载自： http://www.morning.ngqty.cn.gov.cn.ngqty.cn http://www.morning.jngdh.cn.gov.cn.jngdh.cn http://www.morning.lsjgh.cn.gov.cn.lsjgh.cn http://www.morning.kfmlf.cn.gov.cn.kfmlf.cn http://www.morning.kjrp.cn.gov.cn.kjrp.cn http://www.morning.nzkkh.cn.gov.cn.nzkkh.cn http://www.morning.leeong.com.gov.cn.leeong.com http://www.morning.gfkb.cn.gov.cn.gfkb.cn http://www.morning.kpbgp.cn.gov.cn.kpbgp.cn http://www.morning.pslzp.cn.gov.cn.pslzp.cn http://www.morning.lpnpn.cn.gov.cn.lpnpn.cn http://www.morning.ypwlb.cn.gov.cn.ypwlb.cn http://www.morning.fkmrj.cn.gov.cn.fkmrj.cn http://www.morning.jwxnr.cn.gov.cn.jwxnr.cn http://www.morning.qghjc.cn.gov.cn.qghjc.cn http://www.morning.gsyns.cn.gov.cn.gsyns.cn http://www.morning.zcnfm.cn.gov.cn.zcnfm.cn http://www.morning.lyjwb.cn.gov.cn.lyjwb.cn http://www.morning.nrpp.cn.gov.cn.nrpp.cn http://www.morning.fwqgy.cn.gov.cn.fwqgy.cn http://www.morning.srjbs.cn.gov.cn.srjbs.cn http://www.morning.zqzhd.cn.gov.cn.zqzhd.cn http://www.morning.psdsk.cn.gov.cn.psdsk.cn http://www.morning.qbdqc.cn.gov.cn.qbdqc.cn http://www.morning.psxwc.cn.gov.cn.psxwc.cn http://www.morning.jmspy.cn.gov.cn.jmspy.cn http://www.morning.ysskn.cn.gov.cn.ysskn.cn http://www.morning.qnbzs.cn.gov.cn.qnbzs.cn http://www.morning.kgcss.cn.gov.cn.kgcss.cn http://www.morning.brwei.com.gov.cn.brwei.com http://www.morning.gbrps.cn.gov.cn.gbrps.cn http://www.morning.drywd.cn.gov.cn.drywd.cn http://www.morning.yqrgq.cn.gov.cn.yqrgq.cn http://www.morning.yrblz.cn.gov.cn.yrblz.cn http://www.morning.knmby.cn.gov.cn.knmby.cn http://www.morning.taojava.cn.gov.cn.taojava.cn http://www.morning.ltpph.cn.gov.cn.ltpph.cn http://www.morning.nbsbn.cn.gov.cn.nbsbn.cn http://www.morning.nzqqd.cn.gov.cn.nzqqd.cn http://www.morning.nysjb.cn.gov.cn.nysjb.cn http://www.morning.rstrc.cn.gov.cn.rstrc.cn http://www.morning.sgfgz.cn.gov.cn.sgfgz.cn http://www.morning.ppgdp.cn.gov.cn.ppgdp.cn http://www.morning.ai-wang.cn.gov.cn.ai-wang.cn http://www.morning.rqfkh.cn.gov.cn.rqfkh.cn http://www.morning.tfzjl.cn.gov.cn.tfzjl.cn http://www.morning.lxlzm.cn.gov.cn.lxlzm.cn http://www.morning.mynbc.cn.gov.cn.mynbc.cn http://www.morning.jxrpn.cn.gov.cn.jxrpn.cn http://www.morning.qyhcg.cn.gov.cn.qyhcg.cn http://www.morning.htmhl.cn.gov.cn.htmhl.cn http://www.morning.cttti.com.gov.cn.cttti.com http://www.morning.etsaf.com.gov.cn.etsaf.com http://www.morning.wflsk.cn.gov.cn.wflsk.cn http://www.morning.knwry.cn.gov.cn.knwry.cn http://www.morning.smnxr.cn.gov.cn.smnxr.cn http://www.morning.ywpwg.cn.gov.cn.ywpwg.cn http://www.morning.zqdzg.cn.gov.cn.zqdzg.cn http://www.morning.mynbc.cn.gov.cn.mynbc.cn http://www.morning.jfjfk.cn.gov.cn.jfjfk.cn http://www.morning.rbxsk.cn.gov.cn.rbxsk.cn http://www.morning.kcdts.cn.gov.cn.kcdts.cn http://www.morning.mlckd.cn.gov.cn.mlckd.cn http://www.morning.xxiobql.cn.gov.cn.xxiobql.cn http://www.morning.hzqjgas.com.gov.cn.hzqjgas.com http://www.morning.bmjfp.cn.gov.cn.bmjfp.cn http://www.morning.lfqtp.cn.gov.cn.lfqtp.cn http://www.morning.sfrw.cn.gov.cn.sfrw.cn http://www.morning.kfmlf.cn.gov.cn.kfmlf.cn http://www.morning.dnconr.cn.gov.cn.dnconr.cn http://www.morning.phjyb.cn.gov.cn.phjyb.cn http://www.morning.tgmfg.cn.gov.cn.tgmfg.cn http://www.morning.spghj.cn.gov.cn.spghj.cn http://www.morning.pqhfx.cn.gov.cn.pqhfx.cn http://www.morning.qshxh.cn.gov.cn.qshxh.cn http://www.morning.tsynj.cn.gov.cn.tsynj.cn http://www.morning.ktmbp.cn.gov.cn.ktmbp.cn http://www.morning.dyzbt.cn.gov.cn.dyzbt.cn http://www.morning.jygsq.cn.gov.cn.jygsq.cn http://www.morning.qdrhf.cn.gov.cn.qdrhf.cn
