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.
题面如上简单的说，就是要求子区间的最大和O(n) 复杂度的解是使用了 Kadane 算法，这个算法是专门用于求最大子序列的和~
Kadane's algorithm
简单来说，kadane 算法就是，当 index = i 时，
- 如果 sum(a[0:i]) < 0，那么就取 a[i] 作为 sum
- 如果 sum(a[0:i]) > 0，那么就取 sum + a[i] 作为sum
同时，还存在一个变量来记录过程中有过的最大值，因为 sum + a[i]，其中 a[i] 有可能是负数，如果以 sum 作为结果，可能就无法获取到最大的和，思想其实就是 DP 的思想啦~
状态转移方程就是，
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))
}
