33 lines
687 B
Go
33 lines
687 B
Go
|
package main
|
|||
|
|
|
|||
|
|
import (
|
|||
|
|
"fmt"
|
|||
|
|
"math"
|
|||
|
|
)
|
|||
|
|
|
|||
|
|
// maxSubArray 給訂一組數字找到一組子陣列，這組子陣列的總和是最大的，最後 return 總和。
|
|||
|
|
|
|||
|
|
func maxSubArray(nums []int) int {
|
|||
|
|
// 先定義目前最大的數字，最後就回傳這個數字
|
|||
|
|
maxSum := math.MinInt
|
|||
|
|
tmpSum := 0
|
|||
|
|
|
|||
|
|
for _, item := range nums {
|
|||
|
|
tmpSum += item
|
|||
|
|
// 更新 maxSum 為當前最大的子陣列和
|
|||
|
|
maxSum = max(maxSum, tmpSum)
|
|||
|
|
// 如果 tmpSum 小於 0，則重置為 0，從下一個元素重新開始累加
|
|||
|
|
if tmpSum < 0 {
|
|||
|
|
tmpSum = 0
|
|||
|
|
}
|
|||
|
|
}
|
|||
|
|
|
|||
|
|
return maxSum
|
|||
|
|
}
|
|||
|
|
|
|||
|
|
func main() {
|
|||
|
|
nums := []int{-2, 1, -3, 4, -1, 2, 1, -5, 4}
|
|||
|
|
|
|||
|
|
fmt.Println(maxSubArray(nums), maxSubArray(nums) == 6)
|
|||
|
|
}
|