LeetCode: Maximum Subarray

Maximum Subarray

Similar Problems:

• CheatSheet: Leetcode For Code Interview
• CheatSheet: Common Code Problems & Follow-ups
• Tag: #inspiring, #subarray, #classic, #presum, #maxsubarraysum, #kadane

Find the contiguous subarray within an array (containing at least one number) which has the largest sum.

For example, given the array [-2,1,-3,4,-1,2,1,-5,4],
the contiguous subarray [4,-1,2,1] has the largest sum = 6.

click to show more practice.

More practice:
If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.

Github: code.dennyzhang.com

Credits To: leetcode.com

Leave me comments, if you have better ways to solve.

// https://code.dennyzhang.com/maximum-subarray
// Basic Ideas: presum
// Complexity: Time O(n), Space O(n)
func maxSubArray(nums []int) int {
    if len(nums) == 0 { return -1 }
    res := -1 << 31
    min := 0
    for preSum, i :=0, 0; i<len(nums); i++ {
        preSum += nums[i]
        if (res < preSum - min) {
            res = preSum - min
        }
        if (preSum < min) { min = preSum }
    }
    return res
}