2022/04/08

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 を行う

See Also