解法一：暴力法

最长子序和 - 图1

  1. func maxSubArray(nums []int) int {
  2.   res := math.MinInt32
  3.   n := len(nums)
  4.   for i := 0;i < n;i++ {
  5.     for j := i; j < n; j++ {
  6.       count := 0
  7.       for k := i; k < j; k++ {
  8.         count += nums[k]
  9.       }
  10.       if count > res {
  11.         res = count
  12.       }
  13.     }
  14.   }
  15.   return res
  16. }

最长子序和 - 图2

  1. func maxSubArray(nums []int) int {
  2.   res := math.MinInt32
  3.   n := len(nums)
  4.   for i := 0;i < n;i++ {
  5.     count := 0
  6.     for j := i; j < n; j++ {
  7.       count += nums[j]
  8.       if count > res {
  9.         res = count
  10.       }
  11.     }
  12.   }
  13.   return res
  14. }

解法二：分治

  • 取数组中点，最大子序要么在其左侧，要么在其右侧，要么跨越中点，故分为这三种情况
  • 左、右 可以继续分治，指导取值范围足够小（小到只有一个值，也就是左右边界相等）即可返回
  • 跨越中点，从中点往前，往后分别计算其最大值，然后相加即可。

image.png
注：k = log N

  1. func maxSubArray(nums []int) int {
  2.     return getMaxSubarray(nums ,0, len(nums) -1)
  3. }
  5. func getMaxSubarray(nums []int, start , end int) int {
  6.     if start == end {
  7.         return nums[start]
  8.     }
  10.     mid := start + (end - start) >> 1
  11.     leftMax := getMaxSubarray(nums, start, mid)
  12.     rightMax := getMaxSubarray(nums, mid + 1, end)
  13.     corssMax := getCorssMaxSubarray(nums, start, end, mid)
  14.     return max(leftMax, rightMax, corssMax)
  15. }
  17. func getCorssMaxSubarray(nums []int, start, end, mid int) int {
  18.     leftSum := math.MinInt32
  19.     sum := 0
  20.     for i:= mid; i >= start; i-- {
  21.         sum += nums[i]
  22.         leftSum = max(leftSum, sum)
  23.     }
  24.     rightSum := math.MinInt32
  25.     sum = 0
  26.     for i:= mid + 1; i <= end; i++ {
  27.         sum += nums[i]
  28.         rightSum = max(rightSum, sum)
  29.     }
  30.     return (leftSum + rightSum)
  31. }
  34. func max (params ...int) int {
  35.     res := params[0]
  36.     for _, val := range params {
  37.         if val > res {
  38.             res = val
  39.         }
  40.     }
  41.     return res
  42. }

解法三：贪心

从左到右，如果遇到 sum < 0 ，就归零，继续重新累加

  1. func maxSubArray(nums []int) int {
  2.     max := math.MinInt32
  3.     sum := 0
  4.     for _, val := range nums {
  5.         sum += val 
  6.         if sum > max {
  7.             max = sum
  8.         }
  9.         if sum < 0 {
  10.             sum = 0
  11.         }
  12.     }
  13.     return max
  14. }

解法四：DP

image.png

  1. func maxSubArray(nums []int) int {
  2.     n := len(nums)
  3.     dp := make([]int, n)
  4.     dp[0] = nums[0]
  5.     // 表示以数组第一位结束的最大子序和
  6.     res := nums[0]
  7.     for i:= 1; i < n ; i++ {
  8.         dp[i] = max(dp[i-1]+nums[i], nums[i])
  9.         res = max(dp[i], res)
  10.     }
  11.     return res
  12. }
  14. func max(params ...int) int {
  15.     res := math.MinInt32 
  16.     for _, val := range params {
  17.         if val > res {
  18.             res = val
  19.         }
  20.     }
  21.     return res
  22. }

状态优化:

  1. func maxSubArray(nums []int) int {
  2.     n := len(nums)
  3.     dp := nums[0]
  4.     // 表示以数组第一位结束的最大子序和
  5.     res := nums[0]
  6.     for i:= 1; i < n ; i++ {
  7.         dp = max(dp+nums[i], nums[i])
  8.         res = max(dp, res)
  9.     }
  10.     return res
  11. }
  12. func max(params ...int) int {
  13.     res := math.MinInt32 
  14.     for _, val := range params {
  15.         if val > res {
  16.             res = val
  17.         }
  18.     }
  19.     return res
  20. }