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.

題面如上_{簡單的說，就是要求子區(qū)間的最大和}O(n) 復(fù)雜度的解是使用了 Kadane 算法，這個算法是專門用于求最大子序列的和~

Kadane's algorithm

簡單來說，kadane 算法就是，當(dāng) index = i 時，

• 如果 sum(a[0:i]) < 0，那么就取 a[i] 作為 sum
• 如果 sum(a[0:i]) > 0，那么就取 sum + a[i] 作為sum

同時，還存在一個變量來記錄過程中有過的最大值，因為 sum + a[i]，其中 a[i] 有可能是負(fù)數(shù)，如果以 sum 作為結(jié)果，可能就無法獲取到最大的和，思想其實就是 DP 的思想啦~

狀態(tài)轉(zhuǎn)移方程就是，

sum = max(a[i], sum+a[i])
max = max(sum, max)

Solution

package main

import (
    "fmt"
)

func getMax(a int, b int) int {
    if a > b {
        return a
    }
    return b
}

func maxSubArray(nums []int) int {
    // 這里注意需要初始化為 nums[0] 或者一個極小值，不能初始化為 0
    // bad case: [-1] output: 0
    sum, max := nums[0], nums[0]
    for i := 1; i < len(nums); i++ {
        sum = getMax(nums[i], sum + nums[i])
        max = getMax(sum, max)
    }
    return max
}

func main() {
    a := []int{-2,1,-3,4,-1,2,1,-5,4}
    fmt.Println(maxSubArray(a))
}