代码随想录算法训练营day53 | 1143.最长公共子序列，1035.不相交的线，53. 最大子序和
admin
2024-02-12 19:47:30
0次

1143.最长公共子序列

  • 这道题与#718区别在于这里不要求是连续的了，但要有相对顺序，即："ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。
  • 与#718类似，在定义dp数组的时候依然可以按照题解的定义方式，即dp[i][j]：长度为[0, i - 1]的字符串text1与长度为[0, j - 1]的字符串text2的最长公共子序列为dp[i][j]。但是也像在#718有的疑问一样，定义并不直观，那么就按照长度为[0, i]的字符串text1和长度为[0, j]的字符串text2来定义，这样就需要初始化dp数组的第一行和第一列。
  • 具体代码参考#718第三种解法来写。。。

1035.不相交的线

  • 仔细阅读题目发现：直线不能相交，这就是说明在字符串nums1中找到一个与字符串nums2相同的子序列，且这个子序列不能改变相对顺序。只要相对顺序不改变，链接相同数字的直线就不会相交。
  • 本题说是求绘制的最大连线数，其实就是求两个字符串的最长公共子序列的长度！
  • 这就与#1143一模一样了
  • #718，#1143和#1035一起整理复习！！！

53. 最大子序和

五部曲：

  1. 确定dp数组以及下标的含义：dp[i]：包括下标i之前的最大连续子序列和为dp[i]。
  2. 确定递推公式：dp[i] = max(dp[i - 1] + nums[i], nums[i]); 

    因为dp[i]只有两个方向可以推出来：

    1. dp[i - 1] + nums[i]，即：nums[i]加入当前连续子序列和
    2. nums[i]，即：从头开始计算当前连续子序列和
  3. dp数组如何初始化：从递推公式可以看出来dp[i]是依赖于dp[i - 1]的状态，dp[0]就是递推公式的基础。dp[0] = nums[0]
  4. 确定遍历顺序：递推公式中dp[i]依赖于dp[i - 1]的状态，需要从前向后遍历。
  5. 打印检查

词库加载错误:未能找到文件“E:\highferrum_mysql\Configuration\Dict_Stopwords.txt”。

上一篇：诚邀来“电”，衢州等您丨2024电子科技大学长三角研究院（衢州）全球引才计划公布！ 衢州电子科技大学长三角研究院 衢州电子科技大学研究院招聘

下一篇：开分9.4！安志杰和谢苗一联手，就是网大动作片天花板 安志杰谢苗打戏 安志杰和谢苗合作了哪些电影

相关内容

热门资讯

哈易购APP非法期货交易欺骗投... 　　哈易购APP宣传可做白银铂金贵金属订购交易，但实际上并没有取得相关交易资质！哈易购APP本质上就...
消息称百度旗下昆仑芯瞄准500... 6 月 29 日消息，据《The Information》昨日援引知情人士消息，百度旗下 AI 芯片...
打造夏日消费新场景 第35届北... 北京商报讯（记者 翟枫瑞）6月29日消息，第35届北京国际燕京啤酒文化节新闻发布会在京举行。本届啤酒...
社保基金持仓数据出炉，一季度增... 最近各大上市公司一季度财报都公开了，咱们国家社保基金的持仓数据也全部曝光。目前社保拿着比亚迪价值44...
36氪首发 | 海思、中兴团队... 作者 | 乔钰杰 编辑 | 袁斯来 硬氪获悉，广州宸思通讯科技有限公司（以下简称“宸思科技”）近日完...
两天蒸发47亿市值！一纸税务通... 一纸税务通知书，能让一家百亿龙头两天蒸发47亿市值。 6月22日，北大荒（600598.SH）公告称...
SK海力士将投资1100万亿韩... SK集团会长崔泰源6月29日在韩国“三大重大计划”发布会上宣布，公司将投资1100万亿韩元扩大半导体...
两只A股，终止上市！ 两家A股公司，即将摘牌。 6月29日，退市沪科(600608.SH)公告称，上海证券交易所将在202...
原创 M... 一家成立近十年的自动驾驶公司，在IPO时吸引了14家基石投资者认购近一半的发行股份，其中不乏奔驰、比...
基金忠言｜国寿安保滤镜碎，三年... 图片来源：视觉中国 蓝鲸新闻6月29日讯（记者 祁和忠）保险系基金公司国寿安保总经理换人了。 6月2...
三星电机计划加码玻璃基板！相关... 6月29日，玻璃基板概念股午后有所回升， 华工科技（000988.SZ）逼近涨停， 彩虹股份（600...
拉萨海关持续壮大外贸经营主体 ...   新华网拉萨6月28日电（记者蒋梦辰）近日，记者从拉萨海关获悉，今年前5个月，西藏有进出口实绩的外...
机构：二季报临近，医药生物板块... 6月29日，华源证券发布了一篇医药生物行业的研究报告，报告指出，业绩期临近，产业链景气度有望再次迎来...
每日收评科创50放量涨超4.5... 财联社6月29日讯，三大指数全线收红，创业板指探底回升，科创50指数大涨4.61%。沪深两市成交额3...
6月多地土拍结构性升温：深圳单... 进入2026年6月，不少城市核心区地块集中诞生高溢价宗地，热度突出的城市包含深圳、杭州、长沙。 其中...
业绩炸裂！盛达资源半年预盈3.... 6月29日，贵金属矿山龙头盛达资源（000603.SZ）发布 2026 年半年度业绩预告，上半年业绩...
A股午后拉升三大股指收涨：半导... A股三大股指6月29日开盘涨跌互现。早盘沪强深弱，创指一度跌超2%。半导体午后拉升，带动两市上涨，沪...
原创 空... 前言 大家好，我是老金。 这几天，两幅极度割裂的画面放在一起，把我看笑了。 一边是在持续的热浪下，欧...
白酒板块震荡反弹，酒鬼酒涨停！...
澳大利亚审慎监管局拟放宽银行风... 澳大利亚审慎监管局（APRA）6月29日就修改 银行信用风险资本设定公开征求意见，旨在加大信贷投放以...