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)
|
||
}
|