【アルゴリズム脳トレ】leetcode medium 300 Longest Increasing Subsequence

投稿日：2020年2月16日

こんにちは

今回の学びは

・最初に、全ての一個目をrec(i) for i in range(N)で訪れているのは、何も選んでいない-1のインデックスから再帰をはじめるより

分かりやすいから、と理解した。

問題はlongest-increasing-subsequence

（時間配分は5分問題理解=restate&clarify　10分検討multip-sol, analysis, reasons 10分実装 20分振り返り　の一文45分構成)をできればgoogle docで笑&真剣。

終始、わからないことは声にだして、明確にしていきましょう。

１，まずは入出力をしっかりおさえましょう。（問題を自分の言葉で復唱すること、わからないことをクリアにすると、前提も声にだすこと）

２，いくつかのソリューションを声にだして出してみましょう。（もちろんtime complexit, space complexityの分析や理由を付け加えて）

３，どれでいくか、一緒に決定しましょう。（理由付きでね、よろしく）

timespace analysis (時間とスペースの分析）は　〇〇です

場合によっては、pseudocode（擬似コード）をかいてみてもよい。

どうしても、自分の考えた再帰だとクリアできなかった。筋は間違っていないと思う。

４、実装しましょう。

参考:https://leetcode.com/problems/longest-increasing-subsequence/discuss/138240/Python-dp-recursive-and-nlogn-binary-search-solutions

#https://leetcode.com/problems/longest-increasing-subsequence/discuss/138240/Python-dp-recursive-and-nlogn-binary-search-solutions
class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        # https://leetcode.com/problems/longest-increasing-subsequence/discuss/138240/Python-dp-recursive-and-nlogn-binary-search-solutions
        cache = {}
        
        def rec(i):
            if i == N-1: return 1
            if i in cache: return cache[i]
            ans = 1
            for j in range(i+1, N):
                if nums[i] < nums[j]:
                    ans = max(ans, 1 + rec(j))
            cache[i] = ans
            return ans
        if nums is None or len(nums) == 0: return 0
        N = len(nums)
        return max( [rec(i) for i in range(N)] )

５、エッジケースとサンプルテストを忘れずに！

振り返り

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

二重での配列でかんあげるのではなく、i, jポインターで、maxを探す旅O(N)にでる

参考動画