JunyiCode
3/24/2020 - 1:33 AM

## 53. Maximum Subarray

similar to best buy stock 一个类型：53，152，239

``````/*
Time complexity : o(n)
Note:
1. int res = Integer.MIN_VALUE; or int res = nums[0];都可以，没有overflow
2. 考虑edge case [-2, -1]:
res = Math.max(res, sum);不能只放在if里面
*/

class Solution {
public int maxSubArray(int[] nums) {
if(nums == null || nums.length == 0)
return 0;
int sum = 0;
// int res = Integer.MIN_VALUE; wrong
int res = nums[0];
for(int i = 0; i < nums.length; i++) {
// sum = Math.max(nums[i], sum + nums[i]);
if(sum >= 0)
sum += nums[i];
else
sum = nums[i];
res = Math.max(res, sum);
}
return res;
}
}``````
``````/*
Time complexity : o(nlogn)

-2
-2 1
-2 1 3

The worst case is 0. do not sum the element to the left. it is imopossible to be negative value
int midLeftMax = 0;
int midRightMax = 0;
*/

class Solution {
public int maxSubArray(int[] nums) {
return helper(nums, 0, nums.length - 1);
}

private int helper(int[] nums, int left, int right) {
//boundary
if(left == right)    return nums[left];
if(left > right)    return Integer.MIN_VALUE;

int mid = left + (right - left) / 2;

int leftSum  = helper(nums, left, mid - 1);
int rightSum = helper(nums, mid + 1, right);
int crossSum = crossSum(nums, left, right, mid);

return Math.max(Math.max(leftSum, rightSum), crossSum);
}

private int crossSum(int[] nums, int left, int right, int mid) {
//boundary
if(left == right)   return nums[left];

//The worst case is 0. do not sum the element to the left.
// it is imopossible to be negative value
int midLeftMax = 0;
int midRightMax = 0;
int currentSum = 0;

for(int i = mid - 1; i >= left; i--) {
currentSum += nums[i];
midLeftMax = Math.max(midLeftMax, currentSum);
}

currentSum = 0;
for(int i = mid + 1; i <= right; i++) {
currentSum += nums[i];
midRightMax = Math.max(midRightMax, currentSum);
}

return midLeftMax + nums[mid] + midRightMax;
}

}``````