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.
題面如上簡(jiǎn)單的說(shuō)蘑险，就是要求子區(qū)間的最大和O(n) 復(fù)雜度的解是使用了 Kadane 算法垦写，這個(gè)算法是專門用于求最大子序列的和~
Kadane's algorithm
簡(jiǎn)單來(lái)說(shuō)，kadane 算法就是丹壕，當(dāng) index = i 時(shí)胰丁，
- 如果 sum(a[0:i]) < 0妇押，那么就取 a[i] 作為 sum
- 如果 sum(a[0:i]) > 0拭宁，那么就取 sum + a[i] 作為sum
同時(shí)音瓷，還存在一個(gè)變量來(lái)記錄過(guò)程中有過(guò)的最大值对嚼，因?yàn)?sum + a[i]，其中 a[i] 有可能是負(fù)數(shù)绳慎，如果以 sum 作為結(jié)果纵竖，可能就無(wú)法獲取到最大的和，思想其實(shí)就是 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] 或者一個(gè)極小值靡砌，不能初始化為 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))
}
