Question

16.17. Contiguous Sequence

中文文档

Description

You are given an array of integers (both positive and negative). Find the contiguous sequence with the largest sum. Return the 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.

Solutions

Solution 1: Dynamic Programming

We define $f[i]$ as the maximum sum of a continuous subarray that ends with $nums[i]$. The state transition equation is:

$$ f[i] = \max(f[i-1], 0) + nums[i] $$

where $f[0] = nums[0]$.

The answer is $\max\limits_{i=0}^{n-1}f[i]$.

The time complexity is $O(n)$, and the space complexity is $O(n)$. Here, $n$ is the length of the array.

We notice that $f[i]$ only depends on $f[i-1]$, so we can use a variable $f$ to represent $f[i-1]$, thus reducing the space complexity to $O(1)$.

class Solution:
  def maxSubArray(self, nums: List[int]) -> int:
    ans = f = -inf
    for x in nums:
      f = max(f, 0) + x
      ans = max(ans, f)
    return ans

class Solution {
  public int maxSubArray(int[] nums) {
    int ans = Integer.MIN_VALUE, f = Integer.MIN_VALUE;
    for (int x : nums) {
      f = Math.max(f, 0) + x;
      ans = Math.max(ans, f);
    }
    return ans;
  }
}

class Solution {
public:
  int maxSubArray(vector<int>& nums) {
    int ans = INT_MIN, f = INT_MIN;
    for (int x : nums) {
      f = max(f, 0) + x;
      ans = max(ans, f);
    }
    return ans;
  }
};

func maxSubArray(nums []int) int {
  ans, f := math.MinInt32, math.MinInt32
  for _, x := range nums {
    f = max(f, 0) + x
    ans = max(ans, f)
  }
  return ans
}

function maxSubArray(nums: number[]): number {
  let [ans, f] = [-Infinity, -Infinity];
  for (const x of nums) {
    f = Math.max(f, 0) + x;
    ans = Math.max(ans, f);
  }
  return ans;
}

/**
 * @param {number[]} nums
 * @return {number}
 */
var maxSubArray = function (nums) {
  let [ans, f] = [-Infinity, -Infinity];
  for (const x of nums) {
    f = Math.max(f, 0) + x;
    ans = Math.max(ans, f);
  }
  return ans;
};