ゼロから始めるLeetCode Day18 「53. Maximum Subarray」

概要

海外ではエンジニアの面接においてコーディングテストというものが行われるらしく、多くの場合、特定の関数やクラスをお題に沿って実装するという物がメインである。

どうやら多くのエンジニアはその対策としてLeetCodeなるサイトで対策を行うようだ。

早い話が本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイトであり、海外のテックカンパニーでのキャリアを積みたい方にとっては避けては通れない道である。

と、仰々しく書いてみましたが、私は今のところそういった面接を受ける予定はありません。

ただ、ITエンジニアとして人並みのアルゴリズム力くらいは持っておいた方がいいだろうということで不定期に問題を解いてその時に考えたやり方をメモ的に書いていこうかと思います。

Leetcode

Python3で解いています。
Twitterやってます。

ゼロから始めるLeetCode 目次

前回
ゼロから始めるLeetCode Day18 「53. Maximum Subarray」
次回
ゼロから始めるLeetCode Day20 「134. Gas Station」

問題

53. Maximum Subarray

難易度はeasy。
Top 100 Liked Questionsの一つです。

整数のみの配列numsが与えられます。
その配列から少なくとも1つの数値を含むような合計値が最大値となるようなサブ配列を見つけ、その合計を返す、という問題です。

Input: [-2,1,-3,4,-1,2,1,-5,4],
Output: 6

例えば、nums[3]からnums[6]の連続した要素をすべて足すと、4+(-1)+2+1=6となり、配列の中で最大値になるため、このような計算となります。

解法

動的計画法についてはズブの素人ですが、偶然読んでいた
データ構造とアルゴリズム (新・情報 通信システム工学) (日本語) と
典型的な DP (動的計画法) のパターンを整理 Part 1 ～ ナップサック DP 編 ～
であっ、こうしたら解けそうじゃない！？と思ったので参考にしながら考えてみました。

まず、最大値max_numと一時的な変数tempを用意します。
配列の要素を最初から舐めるように代入していき、仮にtempが0以上であればmax_numとtempと比較し、大きい方がmax_numに代入され、そうでなければtempに0を代入されます。このような流れを書いてみると以下のようになります。

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        temp = 0
        max_num = max(nums)
        for i in range(len(nums)):
            temp += nums[i]
            if temp >= 0:
                max_num = max(max_num,temp)
            else:
                temp = 0
        return max_num
# Runtime: 60 ms, faster than 93.50% of Python3 online submissions for Maximum Subarray.
# Memory Usage: 14.5 MB, less than 5.69% of Python3 online submissions for Maximum Subarray.

動的計画法ってとっつきにくいイメージがあったのであまり読み込んでいなかったのですが、書いてみたらメモリが効率化できて速くなるっぽいのでしっかりと勉強しなおした方が良さそうですね。

良さげな回答があれば追記します。