Leetcode Note: Go - Maximum Subarray

Maximum Subarray - LeetCode
https://leetcode.com/problems/maximum-subarray/

• Go 言語で取り組んだメモ

所感

• 全然わからん
• subarray は、配列の中にある隣り合った要素を切り出した配列のこと。のハズ
• 最大値となる subarray をどう判定していけば良いんだろう・・・

実装準備

func assert(a interface{}, b interface{}) bool {
    if a == b {
        return true
    }
    return false
}

func maxSubArray(nums []int) int {
    return 0    
}

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

回答

Go Solution - LeetCode Discuss
https://leetcode.com/problems/maximum-subarray/discuss/1597369/Go-Solution

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

func maxSubArray(nums []int) int {
	curSum, maxSum := nums[0], nums[0]

	for i := 1; i < len(nums); i++ {
		curSum = max(curSum+nums[i], nums[i])
		maxSum = max(curSum, maxSum)
	}
	return maxSum
}

• func max で大小を比較。大きい方を return
• curSum:
  • 初期値は nums[0]
  • ループの間 curSum + nums[i] か nums[i] の大きい方を代入し続ける
    • nums := []int{-2,1,-3,4,-1,2,1,-5,4} なら…
    • i == 1: max(-2 + 1, 1) => 1
    • i == 2: max(1 - 3, -3) => -2
    • i == 3: max(-2 + 4, 4) => 2
• maxSum:
  • 初期値は nums[0]
  • ループの間 curSum か maxSum の大きい方を代入し続ける
    • nums := []int{-2,1,-3,4,-1,2,1,-5,4} なら…
    • i == 1: max(1, -2) => 1
    • i == 2: max(-2, 1) => 1
    • i == 3: max(4, 1) => 4
• 1つの変数で計算回しつつ、もう1つの変数で最大値を保持しておくという実装
  • curSum で隣り合った要素たちを加算していくことで、複数要素の subarray の合計を算出していく
    • この方法だと、後半に大きい値が集結している場合を判定できないのでは？と思っていたが subarray の都合上問題ないっぽい
    • 結局、順繰りで加算していけば網羅できている
  • maxSum で最大値が更新された場合に、値を保持して、最終的な return を行う