class Solution {
public:
int maxSubArray(vector<int>& nums) {
}
};
53. 最大子数组和
给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
子数组 是数组中的一个连续部分。
示例 1：
输入：nums = [-2,1,-3,4,-1,2,1,-5,4] 输出：6 解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。
示例 2：
输入：nums = [1] 输出：1
示例 3：
输入：nums = [5,4,-1,7,8] 输出：23
提示：
1 <= nums.length <= 105-104 <= nums[i] <= 104
进阶：如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的 分治法 求解。
原站题解
golang 解法, 执行用时: 80 ms, 内存消耗: 8.3 MB, 提交时间: 2023-11-20 00:05:25
func maxSubArray(nums []int) int {
return get(nums, 0, len(nums) - 1).mSum;
}
func pushUp(l, r Status) Status {
iSum := l.iSum + r.iSum
lSum := max(l.lSum, l.iSum + r.lSum)
rSum := max(r.rSum, r.iSum + l.rSum)
mSum := max(max(l.mSum, r.mSum), l.rSum + r.lSum)
return Status{lSum, rSum, mSum, iSum}
}
func get(nums []int, l, r int) Status {
if (l == r) {
return Status{nums[l], nums[l], nums[l], nums[l]}
}
m := (l + r) >> 1
lSub := get(nums, l, m)
rSub := get(nums, m + 1, r)
return pushUp(lSub, rSub)
}
func max(x, y int) int {
if x > y {
return x
}
return y
}
type Status struct {
lSum, rSum, mSum, iSum int
}
javascript 解法, 执行用时: 80 ms, 内存消耗: 49.2 MB, 提交时间: 2023-11-20 00:04:49
/**
* @param {number[]} nums
* @return {number}
*/
var maxSubArray = function(nums) {
let pre = 0, maxAns = nums[0];
nums.forEach((x) => {
pre = Math.max(pre + x, x);
maxAns = Math.max(maxAns, pre);
});
return maxAns;
};
java 解法, 执行用时: 1 ms, 内存消耗: 58.2 MB, 提交时间: 2023-11-20 00:03:49
class Solution {
public int maxSubArray(int[] nums) {
int pre = 0, maxAns = nums[0];
for (int x : nums) {
pre = Math.max(pre + x, x);
maxAns = Math.max(maxAns, pre);
}
return maxAns;
}
}
cpp 解法, 执行用时: 92 ms, 内存消耗: 66.4 MB, 提交时间: 2023-11-20 00:03:08
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int pre = 0, maxAns = nums[0];
for (const auto &x: nums) {
pre = max(pre + x, x);
maxAns = max(maxAns, pre);
}
return maxAns;
}
};
golang 解法, 执行用时: 4 ms, 内存消耗: 3.2 MB, 提交时间: 2021-07-20 10:05:01
func maxSubArray(nums []int) int {
imax := nums[0]
for i := 1; i < len(nums); i++ {
if nums[i] + nums[i-1] > nums[i] {
nums[i] += nums[i-1]
}
if nums[i] > imax {
imax = nums[i]
}
}
return imax
}
python3 解法, 执行用时: 136 ms, 内存消耗: N/A, 提交时间: 2018-08-29 22:40:10
class Solution:
def maxSubArray(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
left = 0
right = len(nums) - 1
maxSum = self.divide(nums, left, right)
return maxSum
def divide(self, nums, left, right):
if left == right:
return nums[left]
center = (left+right)//2
leftMaxSum = self.divide(nums, left, center)
rightMaxSum = self.divide(nums, center+1, right)
leftBorderSum = nums[center]
leftSum = nums[center]
for i in range(center-1, left-1, -1):
leftSum += nums[i]
if leftSum > leftBorderSum:
leftBorderSum = leftSum
rightBorderSum = nums[center+1]
rightSum = nums[center+1]
for i in range(center+2, right+1):
rightSum += nums[i]
if rightSum > rightBorderSum:
rightBorderSum = rightSum
BorderSum = leftBorderSum + rightBorderSum
return max(leftMaxSum, rightMaxSum, BorderSum)
python3 解法, 执行用时: 56 ms, 内存消耗: N/A, 提交时间: 2018-08-29 22:27:01
class Solution:
def maxSubArray(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
l = len(nums)
if l == 1:
return nums[0]
s = 0
m = nums[0]
for i in range(0, l):
if s < 0:
s = 0
s += nums[i]
m = max(m, s)
return m