leetcode/lcci/16.17.Contiguous Sequence

comments	difficulty	edit_url
true	Easy	https://github.com/doocs/leetcode/edit/main/lcci/16.17.Contiguous%20Sequence/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

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).

Python3

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

Java

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

C++

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

Go

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
}

TypeScript

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

JavaScript

/**
 * @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;
};

Swift

class Solution {
    func maxSubArray(_ nums: [Int]) -> Int {
        var ans = Int.min
        var f = Int.min

        for x in nums {
            f = max(f, 0) + x
            ans = max(ans, f)
        }

        return ans
    }
}