Leecode 第53题 Maximum Subarray【分而治之】(Java)

原题:https://leetcode.com/problems/maximum-subarray/

给定一个integer数组nums,找出连续的子数组(至少包含一个数字),其和最大,并返回和。

例子:

Input: [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Explanation: [4,-1,2,1] 拥有最大和 = 6

后续:

如果你找出O(n)的解,请尝试用分而治之方法找出其他解,效率更高。

暴力解

分而治之解法

实际上这个问题是跟《算法导论》介绍的最大数组问题完全一样的问题,我的解法直接使用了,之前实现的算法导论的那个解法

Github 地址:https://github.com/tinyfool/leetcode/tree/master/src/p0053

也请参阅我的文章《LeetCode专题 分而治之》,文章中实现了算法导论里面的这三个分而治之的问题的代码,以及LeetCode相关问题的一个列表。

打赏

发表评论

电子邮件地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据