いいものをつくろう

CTOの日記

アルゴリズム

【アルゴリズム脳トレ】leetcode easy 53 maximum subarray

更新日:

こんにちは

今回の学びは

「次のこの問題を解くばあい知っていればよい一つの事実とは?」でフックを増やせ

・解きまくって量を増やしてひらめきを早くしよう!

で、連続するなになにとくれば、それまでの合計を持ち歩くことができそうです

kadane方式です。index J で終わるサブ配列を考えるのが味噌

 

問題はeasyですが、mediumくらいは有る感じです。

 

(時間配分は5分問題理解 10分検討 10分実装  20分振り返り の一文45分構成)

まずは入出力をしっかりおさえましょう。

 

なんどもサンプルを汚して

ようやく思いつく問題にはどうしたら

もっと早くおもいつくのか?

もっと早くとけるのか?

これには焦らず、量とフックを増やしましょう。(ひらめく方法のググり結果を参照

量はleetcodeやatcoderなどの問題を数多く解くこと

フックは、毎回その問題から「次のこの問題を解くばあい知っていればよい一つの事実とは?」と (※1)

自問してその答えを用意しておこう

持ちろん、本記事のように学びを抽出していくことも効果はあるとおもう。

 

(※1)https://medium.com/@alimirio/how-to-solve-problems-on-leetcode-to-prepare-for-technical-interviews-e74781b865d2参考

実装前後でこれは毎回書きましょう。timespace analysis (時間とスペースの分析)は 

 

実際の実装はこちら

import sys
sys.setrecursionlimit(314159265)
class Solution:
    def maxSubArray(self, nums: List[int]) -> int:

        pre = -sys.maxsize
        i = 0 # left pointer
        total = 0
        maxi = -sys.maxsize
        for j in range(len(nums)):
            curr = nums[j]
            #print("i:%s, j:%s, curr:%s, total:%s" % (i, j, curr, total))
            if total + curr > curr:
                #print("継続")
                total += curr
                maxi = max(maxi, total)
            elif total + curr < curr:
                #print("一回リセットししょ")
                maxi = max(maxi, total)
                total = curr
                maxi = max(maxi, total)
                i = j
            else:
                #print("まぁ継続")
                total += curr
                maxi = max(maxi, total)

            pre = curr
        # 最後にもう一回しておく必要がある
        maxi = max(maxi, total)
        return maxi

 

実装後です。timespace analysis (時間とスペースの分析)は ◯◯

 

 

「次のこの問題を解くばあい知っていればよい一つの事実とは?」

これまで、と現在を比較、悪い過去は切り捨て戦法、となづけました

 

最後に考えがごちゃついている実装なので掃除したバージョンをアップします

こちら

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        total = 0
        maxi = -2147483647
        for j in range(len(nums)):
            curr = nums[j]
            past = total + curr
            if past > curr:
                total += curr
            elif past < curr:
                total = curr
            else:
                total += curr
            maxi = max(maxi, total)

        return maxi

変数大事〜

pastにしただけでだいぶ読みやすくなったし

 

あとこの問題

contiguous(隣接する)とあります

連続すると、捉えてもいいです。

で、連続するなになにとくれば、それまでの合計を持ち歩くことができそうです

 

 

 

と、ここまでが最初の記事だったのですが、この最初の記事から4ヶ月ぶりにこの問題に

再び向かったのですが、残念ながら全く解けませんでしたw。

 

解法はいくつかあります。leetcodeのソリューションはこちらです。

分割統治法(devide and concur)と

greedyと

Dynamic Programming で、このmaxium subarrayにおいては kadane's algorithm という名前がついているものです。

kadane's algorithm は説明動画はこちらがわかりやすかったです。Dynamic Programmingで縦軸に同じく配列を撮って

starting indexとしてi-thからサブ配列を始めた時のmaxSubarrayと自然にしたいところですが、これだとO(N^2)でBFと変わりません。そこで、

要素が連続という点と、うまく以前の結果を再利用という、ヒントから

f(i) = f(i - 1) + nums[i] 的な式を立てたのが、kadane方式です。index J で終わるサブ配列を考えるのが味噌で、

これによってO(N)で処理が終わります

kadaneの実装はこちら

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        N = len(nums)
        if N == 0: return 0
        dp = [0] * N
        dp[0] = nums[0]
        maxi = nums[0]
        for i in range(1, N):
            dp[i] = max(
                dp[i-1] + nums[i],
                nums[i]
            )
            maxi = max(maxi, dp[i])
        return maxi

devide  and concurはこちらの説明動画をみて理解しました。

 

 

 

まとめ

「次のこの問題を解くばあい知っていればよい一つの事実とは?」でフックを増やせ

・解きまくって量を増やしてひらめきを早くしよう!

で、連続するなになにとくれば、それまでの合計を持ち歩くことができそうです

kadane方式です。index J で終わるサブ配列を考えるのが味噌

以上です

-アルゴリズム
-,

Copyright© CTOの日記 , 2020 All Rights Reserved.