0053.maximum-subarray.md

0053.Maximum-Subarray

Description

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.

Tags: Array, Divide and Conquer, Dynamic Programming

题意

给定一个整数数组 nums ，找到和最大的连续子序列（至少包含一个数字），返回该子序列的和

题解

思路1

(动态规划) O(n)

• 1.设 dp(i)dp(i) 表示以第iy个数字为结尾的最大连续子序列的和是多少。
• 2.初始化 dp(0)=nums[0]dp(0)=nums[0]。
• 3.转移方程 dp(i)=max(dp(i−1)+nums[i],nums[i])dp(i)=max(dp(i−1)+nums[i],nums[i])。可以理解为当前有两种决策，一种是将第i个数字和前边的数字拼接起来；另一种是第i个数字单独作为一个新的子序列的开始。
• 4.最终答案为ans=max(dp(k)),0≤k<n。

时间复杂度

• 状态数为 O(n)，决策数为 O(1)，故总时间复杂度为 O(n)。

func maxSubArray(nums []int) int {
    dp, ans := make([]int, len(nums)), nums[0]
    dp[0] = nums[0]

    for i := 1; i < len(nums); i++ {
        dp[i] = max(nums[i], nums[i]+dp[i-1])
        ans = max(dp[i], ans)
    }
    return ans
}

思路2

(分治) O(nlogn)

• 考虑区间 [l, r] 内的答案如何计算，令 mid = (l + r) / 2，则该区间的答案由三部分取最大值，分别是：
  • (1). 区间 [l, mid] 内的答案（递归计算）。
  • (2). 区间 [mid + 1, r] 内的答案（递归计算）。
  • (3). 跨越 mid和mid+1 的连续子序列。
• 其中，第(3)部分只需要从 mid 开始向 l 找连续的最大值，以及从 mid+1 开始向 r 找最大值即可，在线性时间内可以完成。
• 递归终止条件显然是 l==r ，此时直接返回nums[l]。

时间复杂度

• 由递归主定理 S(n)=2S(n/2)+O(n)，解出总时间复杂度为 O(nlogn)。
• 或者每一层时间复杂度是 O(n)，总共有 O(logn) 层，故总时间复杂度是 O(nlogn)。

Code

```go func maxSubArray(nums []int) int { return calc(0, len(nums)-1, nums) }

func calc(l, r int, nums []int) int { if l == r { return nums[l] } mid := (l + r) >> 1 lmax, lsum, rmax, rsum := nums[mid], 0, nums[mid+1], 0

for i := mid; i >= 1; i-- {
    lsum += nums[i]
    lmax = max(lmax, lsum)
}

for i := mid + 1; i <= r; i++ {
    rsum += nums[i]
    rmax = max(rmax, rsum)
}

return max(max(calc(l, mid, nums), calc(mid+1, r, nums)), lmax+rmax)

}

```

结语

如果你同我一样热爱数据结构、算法、LeetCode，可以关注我 GitHub 上的 LeetCode 题解：awesome-golang-algorithm