53. Maximum Subarray

题目：

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.

More practice:

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

链接：https://leetcode.com/problems/maximum-subarray/

2/11/2017, Java

犯的错误：

1. 没有考虑到全是负数的情况，最简单的方法就是把每个值分为两个范围来考虑：负，非负。负值的话与当前sum比较，决定是否重置sum；非负值的话，如果当前sum为负，重置sum

2. max的初始化也可以是nums[0]，min_value更直观，但是都必须保证是对的。

没有做divide and conquer approach

 1 public class Solution {
 2     public int maxSubArray(int[] nums) {
 3         if (nums == null) return 0;
 4         int max = Integer.MIN_VALUE;
 5         int sum = 0;
 6      
 7         for (int i = 0; i < nums.length; i++) {
 8             if (nums[i] >= 0) {
 9                 if (sum < 0) sum = nums[i];
10                 else sum += nums[i];
11                 if (max < sum) max = sum;
12             } else {
13                 if (sum < nums[i]) sum = nums[i];
14                 else sum += nums[i];
15                 if (max < sum) max = sum;
16             }
17         }
18         return max;
19     }
20 }

写法不够好，别人的代码。注意第8，第10行，curMax总是要加上当前值，不管正负，所以下一句第9行可以继续判断。第10行用来排除负的curMax的干扰。

 1 public class Solution {
 2     public int maxSubArray(int[] nums) {
 3         if(nums == null || nums.length == 0)
 4             return 0;
 5         int globalMax = Integer.MIN_VALUE, curMax = 0;
 6         
 7         for(int i = 0; i < nums.length; i++){
 8             curMax += nums[i];
 9             globalMax = Math.max(globalMax, curMax);
10             if(curMax < 0)
11                 curMax = 0;
12         }    
13         
14         return globalMax;
15     }
16 }