### 题目

Find the contiguous subarray within an array (containing at least one number) which has the largest sum.

For example, given the array [-2,1,-3,4,-1,2,1,-5,4], the contiguous subarray [4,-1,2,1] has the largest sum = 6.

### 暴力$O(n^2)$

#### 代码

public class Solution {
public int maxSubArray(int[] nums) {
int max = Integer.MIN_VALUE;
for (int i = 0; i < nums.length; i++) {
int sum = 0;
for (int j = i; j < nums.length; j++) {
sum += nums[j];
if (sum > max) { max = sum; }
}
}
return max;
}
}


### 丢弃所有累计小于等于零的子串 $O(n)$

    指针：[-2]的前缀子串小于零，对后面的累加没有帮助。
|
-2,1,-3,4,-1,2,1,-5,


#### 代码

public class Solution {
public int maxSubArray(int[] nums) {
int max = Integer.MIN_VALUE;
for (int i = 0; i < nums.length; ) {
int cursor = i, temp = 0;
while (cursor < nums.length) {
temp += nums[cursor++];
max = Math.max(max,temp);
if (temp < 0) { break; }
}
i = cursor;
}
return max;
}
}


#### 动态规划思想

public class Solution {
public int maxSubArray(int[] nums) {
int heritage = 0, max = Integer.MIN_VALUE;
for (int i = 0; i < nums.length; i++) {
int assets = heritage + nums[i];
max = Math.max(max,assets);
heritage = Math.max(assets,0); //遗产为负，就是累赘，不如扔掉历史包袱
}
return max;
}
}


public class Solution {
public int maxSubArray(int[] nums) {
int[] max = new int[]{ Integer.MIN_VALUE };
dp(0,max,nums,0);
return max[0];
}
public void dp(int heritage, int[] max, int[] nums, int cursor) { // nums[]数组作为参数是要入栈的，会导致stackoverflow
if (cursor == nums.length) { return; }
int assets = heritage + nums[cursor];
max[0] = Math.max(max[0],assets);
heritage = Math.max(assets,0);
dp(heritage,max,nums,++cursor);
}
}


### 分治法 + 回溯算法，复杂度$O(n^2)$

[1,2,3,4]为例每层递归分为三部分，

1. 左边[1,2]
2. 右边[3,4]
3. 中间合并[1,2,3,4]，以(2,3)为核心，利用回溯算法向两边扩展的所有组合。

#### 代码

public class Solution {
public int maxSubArray(int[] nums) {
if (nums.length == 0) { return 0; }
return dac(nums,0,nums.length-1);
}
public int dac(int[] nums, int low, int high) {
if (low == high) { return nums[low]; }
int mid = low + (high - low) / 2; // 下位中位数
int left = dac(nums,low,mid); // 左半边最大值
int right = dac(nums,mid+1,high); // 右半边最大值
int candidate1 = Math.max(left,right);
int kernel = nums[mid] + nums[mid+1];
int candidate2 = fromMiddle(nums,low,high,mid,mid+1,kernel,kernel); //中间合并区的最大值
return Math.max(candidate1,candidate2);
}
public int fromMiddle(int[] nums, int left, int right, int low, int high, int soFar, int max) {
if (low == left && high == right) { return max; }
int leftMax = Integer.MIN_VALUE;
if (left < low) {
int newSoFar = soFar+nums[low-1];
int newMax = Math.max(max, newSoFar);
leftMax = fromMiddle(nums,left,right,low-1,high,newSoFar,newMax);
}
int rightMax = Integer.MIN_VALUE;
if (right > high) {
int newSoFar = soFar+nums[high+1];
int newMax = Math.max(max,newSoFar);
rightMax = fromMiddle(nums,left,right,low,high+1,newSoFar,newMax);
}
return Math.max(leftMax,rightMax);
}
}