# Maximum Subarray

## Question

Given an array of integers,
find a contiguous subarray which has the largest sum.

Example
Given the array [−2,2,−3,4,−1,2,1,−5,3],
the contiguous subarray [4,−1,2,1] has the largest sum = 6.

Note
The subarray should contain at least one number.

Challenge
Can you do it in time complexity O(n)?


## 题解1 - 贪心

### Java

public class Solution {
/**
* @param nums: A list of integers
* @return: A integer indicate the sum of max subarray
*/
public int maxSubArray(ArrayList<Integer> nums) {
// -1 is not proper for illegal input
if (nums == null || nums.isEmpty()) return -1;

int sum = 0, maxSub = Integer.MIN_VALUE;
for (int num : nums) {
// drop negtive sum
sum = Math.max(sum, 0);
sum += num;
// update maxSub
maxSub = Math.max(maxSub, sum);
}

return maxSub;
}
}


## 题解2 - 动态规划1(区间和)

### Java

public class Solution {
/**
* @param nums: A list of integers
* @return: A integer indicate the sum of max subarray
*/
public int maxSubArray(ArrayList<Integer> nums) {
// -1 is not proper for illegal input
if (nums == null || nums.isEmpty()) return -1;

int sum = 0, minSum = 0, maxSub = Integer.MIN_VALUE;
for (int num : nums) {
minSum = Math.min(minSum, sum);
sum += num;
maxSub = Math.max(maxSub, sum - minSum);
}

return maxSub;
}
}


## 题解3 - 动态规划2(局部与全局)

### Java

public class Solution {
/**
* @param nums: A list of integers
* @return: A integer indicate the sum of max subarray
*/
public int maxSubArray(ArrayList<Integer> nums) {
// -1 is not proper for illegal input
if (nums == null || nums.isEmpty()) return -1;

int size = nums.size();
int[] local = new int[size];
int[] global = new int[size];
local[0] = nums.get(0);
global[0] = nums.get(0);
for (int i = 1; i < size; i++) {
// drop local[i - 1] < 0
local[i] = Math.max(nums.get(i), local[i - 1] + nums.get(i));
// update global with local
global[i] = Math.max(global[i - 1], local[i]);
}

return global[size - 1];
}
}