What is the most efficient algorithm for finding the maximum subarray sum?

本文共计328个文字，预计阅读时间需要2分钟。

给定一个整数数组nums，找到具有最大和的连续子数组（至少包含一个数字）并返回其和。示例：输入：[-2,1,-3,4,-1,2,1,-5,4]，输出：6。解释：[4,-1,2,1]具有最大的和=6。

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

Example:

Input: [-2,1,-3,4,-1,2,1,-5,4],
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.

Follow up:

If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.

class Solution {
public int maxSubArray(int[] nums) {
int maxSum = Integer.MIN_VALUE;
int curSum = 0;
int left = 0, right = 0;
while (right < nums.length) {
curSum += nums[right];
maxSum = Math.max(maxSum, curSum);
right++;
if (curSum < 0) {
curSum = 0;
left = right;
}
}
return maxSum;
}
}public class Solution {
public int maxSubArray(int[] nums) {
int currSum = nums[0], maxSum = nums[0];

for(int i = 1; i < nums.length; i++) {

currSum = (currSum < 0) ? nums[i] : (currSum + nums[i]);

if (currSum > maxSum) {
maxSum = currSum;
}
}

return maxSum;
}
}class Solution:
def maxSubArray(self, nums: List[int]) -> int:
res = nums[0]
cur = nums[0]
for i in range(1, len(nums)):
cur += nums[i]
if cur < nums[i]:
cur = nums[i]
res = max(res, cur)
return res