README_EN.md

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

Python3

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        n = len(nums)
        dp = [0] * n
        dp[0] = nums[0]
        for i in range(1, n):
            dp[i] = max(dp[i - 1], 0) + nums[i]
        return max(dp)

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

Java

class Solution {
    public int maxSubArray(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n];
        dp[0] = nums[0];
        int ans = dp[0];
        for (int i = 1; i < n; ++i) {
            dp[i] = Math.max(dp[i - 1], 0) + nums[i];
            ans = Math.max(ans, dp[i]);
        }
        return ans;
    }
}

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

C++

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int n = nums.size();
        vector<int> dp(n);
        dp[0] = nums[0];
        int ans = dp[0];
        for (int i = 1; i < n; ++i) {
            dp[i] = max(dp[i - 1], 0) + nums[i];
            ans = max(ans, dp[i]);
        }
        return ans;
    }
};

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

Go

func maxSubArray(nums []int) int {
	n := len(nums)
	dp := make([]int, n)
	dp[0] = nums[0]
	ans := dp[0]
	for i := 1; i < n; i++ {
		dp[i] = max(dp[i-1], 0) + nums[i]
		ans = max(ans, dp[i])
	}
	return ans
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

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

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

JavaScript

/**
 * @param {number[]} nums
 * @return {number}
 */
var maxSubArray = function (nums) {
    const n = nums.length;
    const dp = new Array(n).fill(0);
    dp[0] = nums[0];
    let ans = dp[0];
    for (let i = 1; i < n; ++i) {
        dp[i] = Math.max(dp[i - 1], 0) + nums[i];
        ans = Math.max(ans, dp[i]);
    }
    return ans;
};

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

...