LeetCodeに毎日挑戦してみた 53. Maximum Subarray（Python、Go）

はじめに

無料英単語サイトE-tanを運営中の@ishishowです。

プログラマとしての能力を上げるために毎日leetcodeに取り組み、自分なりの解き方を挙げていきたいと思います。

Leetcodeとは

leetcode.com
ソフトウェア開発職のコーディング面接の練習といえばこれらしいです。
合計1500問以上のコーデイング問題が投稿されていて、実際の面接でも同じ問題が出されることは多いらしいとのことです。

golang入門＋アルゴリズム脳の強化のためにgoとPythonで解いていこうと思います。(Pythonは弱弱だが経験あり)

12問目（問題53)

53. Maximum Subarray

問題内容

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

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.

（日本語訳）

整数配列が与えられた場合nums、合計が最大である連続するサブ配列（少なくとも1つの数値を含む）を見つけて、その合計を返します。

フォローアップ：O(n)解決策 を見つけた場合は、分割統治法を使用して別の解決策をコーディングしてみてください。これはより微妙です。

Example 1:

  Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
  Output: 6
  Explanation: [4,-1,2,1] has the largest sum = 6.

Example 2:

  Input: nums = [1]
  Output: 1

Example 3:

  Input: nums = [0]
  Output: 0

Example 4:

  Input: nums = [-1]
  Output: -1

Example 5:

  Input: nums = [-2147483647]
  Output: -2147483647

Constraints:

• 1 <= nums.length <= 2 * 104
• -231 <= nums[i] <= 231 - 1

考え方

1. 配列の一つ前の数字が正か負か判断する

2. もし正なら、現在の数字にその数字を足す、負ならそのまま

3. ループ後に変更した配列の中で一番大きい数字を戻り値として返す

• 解答コード

for i in range(1, len(nums)):
        if nums[i-1] > 0:
            nums[i] += nums[i-1]
    return max(nums)

• Goでも書いてみます！

func maxSubArray(nums []int) int {
    for i:=1; i<len(nums); i++{
        if nums[i-1] > 0 {
            nums[i] += nums[i-1]
        }
    }
    return max_num(nums)
}

func max_num(nums []int) int {
    max := nums[0]
    for _, num:= range nums {
        if max < num {
            max = num    
        }
    }
    return max
}