53.Maximum-Subarray

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.
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;
  }
}