# [LeetCode] 53. Maximum Subarray 最大子数组

2021年09月15日 阅读数：1

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

Example:java

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

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

Java:url

```public class Solution {
public int maxSubArray(int[] nums) {
int res = Integer.MIN_VALUE, curSum = 0;
for (int num : nums) {
curSum = Math.max(curSum + num, num);
res = Math.max(res, curSum);
}
return res;
}
}
```

Java: Divide and conquercode

```public class Solution {
public int maxSubArray(int[] nums) {
if (nums.length == 0) return 0;
return helper(nums, 0, nums.length - 1);
}
public int helper(int[] nums, int left, int right) {
if (left >= right) return nums[left];
int mid = left + (right - left) / 2;
int lmax = helper(nums, left, mid - 1);
int rmax = helper(nums, mid + 1, right);
int mmax = nums[mid], t = mmax;
for (int i = mid - 1; i >= left; --i) {
t += nums[i];
mmax = Math.max(mmax, t);
}
t = mmax;
for (int i = mid + 1; i <= right; ++i) {
t += nums[i];
mmax = Math.max(mmax, t);
}
return Math.max(mmax, Math.max(lmax, rmax));
}
}
```

Python:htm

```class Solution(object):
def maxSubArray(self, nums):
if max(nums) < 0:
return max(nums)
global_max, local_max = 0, 0
for x in nums:
local_max = max(0, local_max + x)
global_max = max(global_max, local_max)
return global_max
```

Python: wo

```class Solution(object):
def maxSubArray(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
dp = [0] * (len(nums) + 1)
max_sum = float('-inf')  # cannot set max_sum = 0, error when input is [-1]
for i in xrange(1, len(nums) + 1):
if dp[i-1] >= 0:
dp[i] = dp[i-1] + nums[i-1]
else:
dp[i] = nums[i-1]
max_sum = max(max_sum, dp[i])

return max_sum 　　```

Python: wo

```class Solution(object):
def maxSubArray(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
dp = [0] * len(nums)
# res = float('-inf') # error [1]
dp[0] = nums[0]
res = dp[0]
for i in xrange(1, len(nums)):
dp[i] = nums[i] + max(0, dp[i-1])
res = max(res, dp[i])

return res 　　```

C++:

```class Solution {
public:
int maxSubArray(vector<int>& nums) {
int res = INT_MIN, curSum = 0;
for (int num : nums) {
curSum = max(curSum + num, num);
res = max(res, curSum);
}
return res;
}
};
```

C++: Divide and conquer

```class Solution {
public:
int maxSubArray(vector<int>& nums) {
if (nums.empty()) return 0;
return helper(nums, 0, (int)nums.size() - 1);
}
int helper(vector<int>& nums, int left, int right) {
if (left >= right) return nums[left];
int mid = left + (right - left) / 2;
int lmax = helper(nums, left, mid - 1);
int rmax = helper(nums, mid + 1, right);
int mmax = nums[mid], t = mmax;
for (int i = mid - 1; i >= left; --i) {
t += nums[i];
mmax = max(mmax, t);
}
t = mmax;
for (int i = mid + 1; i <= right; ++i) {
t += nums[i];
mmax = max(mmax, t);
}
return max(mmax, max(lmax, rmax));
}
};
```

[LeetCode] 70. Climbing Stairs 爬楼梯

[Airbnb] Max Sum of Non-consecutive Array Elements