53. Maximum Subarray

Problem

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.

Problem Summary

Given an integer array nums, find the contiguous subarray with the largest sum (the subarray must contain at least one element) and return its maximum sum.

Solution Approach

• This problem can be solved with DP or without DP.
• The problem asks for the maximum value of the sum of numbers within some interval in the array. dp[i] represents the maximum sum among all subarrays within the [0,i] interval. The state transition equation is dp[i] = nums[i] + dp[i-1] (dp[i-1] > 0), dp[i] = nums[i] (dp[i-1] ≤ 0).

Code

package leetcode

// Solution 1 DP
func maxSubArray(nums []int) int {
	if len(nums) == 0 {
		return 0
	}
	if len(nums) == 1 {
		return nums[0]
	}
	dp, res := make([]int, len(nums)), nums[0]
	dp[0] = nums[0]
	for i := 1; i < len(nums); i++ {
		if dp[i-1] > 0 {
			dp[i] = nums[i] + dp[i-1]
		} else {
			dp[i] = nums[i]
		}
		res = max(res, dp[i])
	}
	return res
}

// Solution 2 Simulation
func maxSubArray1(nums []int) int {
	if len(nums) == 1 {
		return nums[0]
	}
	maxSum, res, p := nums[0], 0, 0
	for p < len(nums) {
		res += nums[p]
		if res > maxSum {
			maxSum = res
		}
		if res < 0 {
			res = 0
		}
		p++
	}
	return maxSum
}