剑指 Offer 42. 连续子数组的最大和 / LeetCode 53. 最大子数组和 （动态规划）
创始人
2025-05-29 00:49:15
0次

题目：

链接：剑指 Offer 42. 连续子数组的最大和；
LeetCode 53. 最大子数组和
难度：简单

输入一个整型数组，数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。

要求时间复杂度为O(n)。

示例1:

输入: nums = [-2,1,-3,4,-1,2,1,-5,4]
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。

提示：

  • 1 <= arr.length <= 10^5
  • -100 <= arr[i] <= 100

动态规划法：

dp[i] 状态定义：以 nums 数组第 i 位为结尾的最大子数组和。

状态转移方程：dp[i] = max(dp[i - 1] + nums[i], nums[i])
在遍历过程中 dp[i] 有两种选择：要么与前面相邻最大子数组连接形成新的更大子数组；要么抛弃前面的最大子数组，自己独自形成最大子数组。

base case：dp[0] = nums[0]
遍历第一个值初始时只能单独作为一个子数组。

最终，dp 数组中存储了以每一个nums值为结尾的最大子数组，从中找出最大值即可。

代码：

class Solution {
public:int maxSubArray(vector& nums) {int n = nums.size();vector dp(n);int ans = nums[0];// base casedp[0] = nums[0];// 状态转移方程for(int i = 1; i < n; ++i){dp[i] = max(dp[i - 1] + nums[i], nums[i]);}for(int i = 0; i < n; ++i){ans = max(ans, dp[i]);}return ans;}
};

时间复杂度O(n），空间复杂度O(n)。

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

上一篇：利用Mysql定时+存储过程创建临时表统计数据

下一篇：动静态库【Linux】

相关内容

热门资讯

FIBA期待杨瀚森表现 最新实... 北京时间6月25日消息，FIBA国际篮联公布了最新一期世界杯预选赛亚太区球队实力榜，中国男篮排在澳大...
收评：创业板指放量反弹涨2.8... 市场冲高回落后，再度震荡拉升。黄白线分化明显，权重股走势较强。量能明显放大，沪深两市成交额3.59万...
巨头财报引爆A股存储芯片板块，... 当地时间6月24日美股盘后， 美光科技（MU.US）公布截至5月31日的2026财年第三财季财报，业...
银行、消金公司助贷余额增速不得... 近日，中国证券报记者从多位业内人士处独家获悉，5月以来，多地金融监管部门对部分中小银行、消金公司下达...
朱鸿接任陈航，担任钉钉科技有限... 消费日报-今朝新闻讯 天眼查显示，6月23日，钉钉科技有限公司发生工商变更，陈航卸任法定代表人、董事...
3日累跌超20%，德创环保：公... 6月25日， 德创环保（603177.SH）公告，公司股票于2026年6月23日、6月24日和6月2...
北京发布2026年第七轮拟供商... 央广网北京6月25日消息（记者门庭婷）6月25日，北京市规划和自然资源委员会网站发布了2026年第七...
开放麦 | 启明创投胡奇：从A... “2026年，创投圈的浪潮再次翻涌：AI从技术概念走进产业深水区，硬科技创业从“小众赛道” 变成“主...
腾讯孙忠怀：在行业转身处 6月24日，2026腾讯视频年度发布在上海举行。腾讯公司副总裁、腾讯在线视频董事长孙忠怀以《在行业转...
加息，突变！美联储，重磅传来！... 美联储政策路径突生变数。 美国商务部经济分析局最新公布的数据显示，5月个人消费支出（PCE）物价指数...
6月合肥上门收金必看！5步避坑... 2026年6月，合肥黄金市场持续高位运行，不少市民翻出家里闲置的旧金饰、投资金条想变现，上门回收因为...
潮汕女富豪挂帅后加码液冷！祥鑫... 潮汕女强人，带着百亿公司加码液冷散热。 6月24日晚间，祥鑫科技(002965.SZ)公告称，公司董...
马斯克向太空要电，GobiX ... 一场关于「去哪里找电」的全球竞赛，正在朝两个方向展开。 作者｜周永亮 编辑｜ 郑玄 「太空光伏是不是...
原料药行业陷入周期低谷 有药企... 每经记者｜许立波 每经编辑｜魏文艺 “过完年到现在，我们整个团队每个月都在出差，跑遍了亚非拉、欧美市...
家门口筛查白内障！永顺泽家镇暖... 大众卫生报·新湖南客户端6月25日讯（通讯员 彭雪姣）为切实解决辖区老年性白内障患者异地就医奔波、就...
终于等到！油价马上再大跌，这个... 点击添加图片描述（最多60个字） 编辑 各位车主朋友，好消息接二连三！ 继6月18日油价大幅下调...
丈量出海新路 世界酒庄影响力指... 长期以来，全球酒庄评价体系由西方机构主导，且大多局限于单一酒种、单一评价维度，这一局面正逐渐被打破。...
峰瑞资本创始合伙人李丰：从资本... “2026年，创投圈的浪潮再次翻涌：AI从技术概念走进产业深水区，硬科技创业从“小众赛道” 变成“主...
原创 A... 迈向成熟，还有茁壮成长的机会。 作者 | 方璐 编辑丨于婞 来源 | 野马财经 2026年6月21日...
为企业解锁出海新通道！亚太中小... 6月24日下午，作为2026年APEC中小企业工商论坛的重要组成部分，亚太中小企业国际化合作发展论坛...