代码随想录算法训练营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！安志杰和谢苗一联手，就是网大动作片天花板 安志杰谢苗打戏 安志杰和谢苗合作了哪些电影

相关内容

热门资讯

一季度增长12.2%后，王莉定... 来源：茅台时空 据茅台官微报道，茅台酱香系列酒一季度交出营业收入78.8亿元、同比增长12.2%的成...
曦智科技沈亦晨：将与上海国资联... 曦智科技创始人、董事长沈亦晨 图片来源：主办方供图 5月10日，上海曦智科技创始人、董事长沈亦晨出现...
东实环境“还贷式IPO”困境：... 图源：图虫创意 来源|时代商业研究院 作者|特约研究员赖钧洪、郑琳 编辑|郑琳 作为东莞市国资委10...
为什么是宁波？扛起中国五金出口... 中国作为全球最大的五金制品生产国和出口国，正以绿色转型、品牌出海为方向，在全球五金供应链中占据核心地...
AI产业链融资潮 记者观察：全...
微信：关于开展涉税虚假宣传信息... 近期，平台接到用户投诉举报，发现个别账户发布“纳税15万，国家补贴5万”“4月恢复核定征收”等涉税虚...
央视调查：AI“买家秀”误导消... IT之家 5 月 10 日消息，据央视新闻今日报道，在网购场景中，由于消费者无法直接接触商品，所以评...
（机遇香港）“温情经济”升温 ... 中新社香港5月10日电 (记者 邱兆翔)5月10日是母亲节。在香港，不少子女与父母一早出门饮茶庆祝，...
原创 3... 5月8日，彭博社一段视频访谈把华尔街炸了。有"新债王"之称的双线资本创始人冈拉克，公开承认自己已经在...
网点关停潮？一半全国性银行机构... 营业网点是商业银行经营的最小细胞，也是直接触达客户、创造价值的核心战场，其竞争力直接关系到银行经营效...
粮农组织：战火阴影下4月全球食... 来源：财联社 联合国粮农组织（FAO）周五指出，由于中东局势紧张及霍尔木兹海峡反复被封，全球粮食价格...
原创 帮... 老铁们，帮主又来了。今天聊个事儿，保证让你觉得，原来国家战略离你的钱包可以这么近！四部门刚发了个文，...
吸引全球资本，亚洲新一轮“超级... 投资者正将目光转向亚洲，寻找全球股市上涨行情的下一个突破口。 在人工智能浪潮驱动下，韩国股市本月涨幅...
越秀区多维经营账服务细致入微的... 越秀区多维经营账服务细致入微的代理机构参考 在广州越秀区这一商贸活跃的核心区域，中小企业对财税服务...
教人挣钱的自媒体平台叫什么 教人挣钱的自媒体平台叫什么？这问题问得太到位了。说实话，我也曾经翻遍全网、踩过无数坑，就为了找一个真...
湖人被无情戏耍又是三节崩 里夫... 与雷霆的半决赛打到第三场，一种无望的情绪已彻底裹挟了湖人全队，彻底无法被摆脱了。 所有人都清楚，湖人...
原创 欧... 据环球网综合报道，欧盟正处于前所未有的抉择压力之下。在俄乌冲突延续近四年的沉重阴影下，欧盟内部关于援...
原创 1... 雷达财经出品 文|丁禹 编|孟帅 五一假期刚刚结束，市值百亿的川酒上市公司水井坊，其核心管理层再次迎...
美银Hartnett：材料板块... 美银证券首席投资策略师Michael Hartnett在最新报告中点名材料板块，称其将是下一个“牛市...
情绪消费的好日子，还剩多久 文｜强调Next 2025年是中国潮玩行业最热闹的一年，也是从业者最难熬的一年。 热闹是真的热闹。...