Leetcode - 最大子序和
发布日期:2021-07-01 00:15:02
浏览次数:2
分类:技术文章
本文共 543 字,大约阅读时间需要 1 分钟。
题目描述
给定一个整数数组 nums
,找到一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。
示例:
输入: [-2,1,-3,4,-1,2,1,-5,4],输出: 6解释: 连续子数组 [4,-1,2,1] 的和最大,为 6。
进阶:
如果你已经实现复杂度为 O(n) 的解法,尝试使用更为精妙的分治法求解。
解题思路
可以先判断上一项的最大和是否大于0,如果大于0,肯定是越加越大的,否则就再从该项开始一个新的子序列。具体见代码:
#define max(a, b) a > b ? a : bint maxSubArray(int* nums, int numsSize) { int dp[numsSize + 5], max; max = dp[0] = nums[0]; for (int i = 1; i < numsSize; i++) { if (dp[i - 1] < 0) dp[i] = nums[i]; else dp[i] = dp[i - 1] + nums[i]; max = max(max, dp[i]); } return max;}
转载地址:https://lzyws739307453.blog.csdn.net/article/details/84297093 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
留言是一种美德,欢迎回访!
[***.207.175.100]2024年04月09日 13时58分34秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
TensorFlow btc allocator
2019-05-01
3D点云图实验
2019-05-01
linux设备驱动的实现与理解
2019-05-01
python遇到‘\u’开头的unicode编码
2019-05-01
RedHat Linux网络配置
2019-05-01
Linux下如何退出图形界面?
2019-05-01
关于C语言中的结构体对齐
2019-05-01
数据恢复过程中需要注意的一些问题
2019-05-01
const int *p,const * int p,int const *p
2019-05-01
解析大端模式和小端模式
2019-05-01
C++ 使用delete删除指针后应该做的工作
2019-05-01
内存区划分、内存分配、常量存储区、堆、栈、自由存储区、全局区[C++][内存管理]...
2019-05-01
define入门
2019-05-01
头文件中 #ifndef---#define---#endif的作用
2019-05-01
分析Linux内核启动过程:从start_kernel到init
2019-05-01
系统调用过程的理解
2019-05-01
LeetCode 96 Unique Binary Search Trees 解题报告
2019-05-01
LeetCode 136 Single Number解题报告
2019-05-01