首页 > 其他 > 详细

LeetCode刷题记(13)—最大子序和

时间:2019-09-12 22:45:27      阅读:96      评论:0      收藏:0      [点我收藏+]

题目要求:

给定一个整数数组 nums ,找到一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。

示例:

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

题解:

(1)直接思路1:暴力求解,内外循环两次:

技术分享图片

 

 

 (2)经典思路:动态规划:边界是nums[0],状态转移公式是:sum = max(nums[i],sum+nums[i]);遍历一次,时间复杂度为O(n)

技术分享图片

 

 (3)分支算法:时间复杂度为O(nlogn):直接在leecode上编辑器跑不出来,在IDEA上跑出来了,主要是左右两部分递归,中间部分求和,代码如下:

技术分享图片

 

LeetCode刷题记(13)—最大子序和

原文:https://www.cnblogs.com/wangjm63/p/11514773.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!