# 53. Maximum Subarray 最大子数组和

## # 题目描述

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.
``````

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

## # 解题方法

### # 暴力解法

C++代码如下：

``````class Solution {
public:
int maxSubArray(vector<int>& nums) {
const int N = nums.size();
vector<int> preSum(N + 1, 0);
for (int i = 0; i < N; ++i) {
preSum[i + 1] = preSum[i] + nums[i];
}
int res = INT_MIN;
for (int i = 0; i < N + 1; ++i) {
for (int j = i + 1; j < N + 1; ++j) {
res = max(res, preSum[j] - preSum[i]);
}
}
return res;
}
};
``````

### # 动态规划

1. `dp[i] = dp[i - 1] + nums[i]` 当 nums[i] >= 0 。
2. `dp[i] = nums[i]` 当 nums[i] < 0 。

Java 代码如下：

``````public class Solution {
public int maxSubArray(int[] nums) {
int len = nums.length;
int[] dp = new int[len];
dp[0] = nums[0];
int max = dp[0];
for(int i = 1; i < len; i++){
dp[i] = nums[i] + (dp[i -1] > 0 ? dp[i -1] : 0);
max = Math.max(max, dp[i]);
}
return max;
}
}
``````

``````class Solution(object):
def maxSubArray(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
if not nums: return 0
N = len(nums)
cur, prev = 0, 0
res = float("-inf")
for i in range(N):
cur = nums[i] + (prev if prev > 0 else 0)
prev = cur
res = max(res, cur)
return res
``````

``````class Solution {
public:
int maxSubArray(vector<int>& nums) {
const int N = nums.size();
int res = nums[0];
vector<int> dp(N, 0); // 以i为结尾的最大子数组的max subarray.
dp[0] = nums[0];
for (int i = 1; i < N; ++i) {
dp[i] = nums[i] + (dp[i - 1] > 0 ? dp[i - 1] : 0);
res = max(res, dp[i]);
}
return res;
}
};
``````

## # 日期

2017 年 5 月 2 日 2018 年 11 月 19 日 —— 周一又开始了 2020 年 4 月 3 日 —— 这个题是英文版leetcode的每日一题