Comment on page

53.Maximum-Subarray

53. 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.
Follow up:
​
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;
}
}