/*MaximumSubarray.java

Maximum Subarray

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)?

Tags Greedy Enumeration LintCode Copyright LinkedIn Subarray Array

*/

public class MaximumSubarray {

/**

* @param nums: A list of integers

* @return: A integer indicate the sum of max subarray

*/

public int maxSubArray(int[] nums) {

// write your code

if (nums == null || nums.length == 0) {

return 0;

}

int maxSum = Integer.min;

int sum = 0;

int minSum = 0;

for (int i = 0; i <nums.length();i++) {

sum += nums[i];

maxSum = Math.max(maxSum, sum - minSum);

minSum = Math.min(sum, minSum);

}

return maxSum;

}

}