# 53.Maximum-Subarray

## ้ข็ฎๅฐๅ

https://leetcode.com/problems/maximum-subarray/

## ้ข็ฎๆ่ฟฐ

``````Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

Example:

Input: [-2,1,-3,4,-1,2,1,-5,4],
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.

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

## ไปฃ็ 

### Approach #1 Greedy

• Time complexity : O(N) since it's one pass along the array

• Space complexity : O(1), since it's a constant space solution

``````public class Solution {
public int maxSubArray(ArrayList<Integer> nums) {
if (nums == null || nums.isEmpty()) return -1;

int sum = 0;
int maxSum = Integer.MIN_VALUE;
for (int num : nums) {
sum = Math.max(sum, 0);
sum += num;
// sum = Math.max(num, sum + num);

maxSum = Math.max(maxSum, sum);
}

return maxSum;
}
}``````

### Approach #2 Max = Sum - minSum

``````public class Solution{
public int maxSubArray(ArrayList<Integer> nums){
if (nums == null || nums.isEmpty()) return -1;

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

return maxSub;
}
}``````

### Approach #3 Dynamic Programming

`local[]` ๅฑ้จๆๅฐๅผ `Math.max(nums.get(i), local[i - 1] + nums.get(i))`

`global[]` ๅจๅฑๆๅคงๅผ `Math.max(global[i - 1], local[i])`

``````public class Solution {
public int maxSubArray(ArrayList<Integer> nums){
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];
}
}``````

### Approach 4: Divide & Conquer

Time complexity : `O(NlogN)`. && Space complexity : `O(logN)`

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

public int helper(int[] nums, int left, int right) {
if (left == right) return nums[left];

int middle = (left + right) / 2;

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

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

public int crossSum(int[] nums, int left, int right, int middle) {
if (left == right)    return nums[left];

int leftSubSum = Integer.MIN_VALUE;
int currSum = 0;
for (int i = middle; i >= left; i--) {
currSum += nums[i];
leftSubSum = Math.max(leftSubSum, currSum);
}

int rightSubSum = Integer.MIN_VALUE;
currSum = 0;
for (int i = middle + 1; i <= right; i++) {
currSum += nums[i];
rightSubSum = Math.max(rightSubSum, currSum);
}

return leftSubSum + rightSubSum;
}
}``````

Last updated