How do I memoize this LIS python2.7 algorithm properly?
<p>I'm practicing Dynamic Programming and I am writing the Longest Increasing Subsequence problem.</p>

<p>I have the DP solution:</p>

<pre><code>def longest_subsequence(lst, lis=[], mem={}):
  if not lst:
    return lis
  if tuple(lst) not in mem.keys():
    if not lis or lst[0] &gt; lis[-1]:
      mem[tuple(lst)] = max([longest_subsequence(lst[1:], lis+[lst[0]], mem), longest_subsequence(lst[1:], lis, mem)], key=len)
    else:
     mem[tuple(lst)] = longest_subsequence(lst[1:], lis, mem)
  return mem[tuple(lst)]
</code></pre>

<p>And a non-memoized version</p>

<pre><code>def longest_subsequence(lst, lis=[]):
  if not lst:
    return lis
  if not lis or lst[0] &gt; lis[-1]:
    result = max([longest_subsequence(lst[1:], lis+[lst[0]]), longest_subsequence(lst[1:], lis)], key=len)
  else:
    result = longest_subsequence(lst[1:], lis)
  return result
</code></pre>

<p>However, the two functions have different behaviours. For example, the test case <code>longest_subsequence([10,9,2,5,3,7,101,18])</code> fails for the memoized version. </p>

<pre><code>&gt;&gt;&gt; longest_subsequence([10,9,2,5,3,7,101,18])
[10, 101]
</code></pre>

<p>The non-memoized version is fully correct however (although much slower). </p>

<pre><code>&gt;&gt;&gt; longest_subsequence([10,9,2,5,3,7,101,18])
[2, 5, 7, 101]
</code></pre>

<p>what I am doing wrong?</p>

<p><strong>EDIT:</strong> Tempux's answer fails on the following:</p>

<pre><code>&gt;&gt;&gt; longest_subsequence([3,5,6,2,5,4,19,5,6,7,12])
[3, 5, 6, 7, 12]
</code></pre>

<p>where the solution the non-memoized version is:</p>

<pre><code>&gt;&gt;&gt; longest_subsequence([3,5,6,2,5,4,19,5,6,7,12])
[3, 4, 5, 6, 7, 12]
</code></pre>

<p>So I had just discovered that Tempux's answer did not work for all cases.</p>

<p>I went back and through about encapsulating the entire state into the memoization dictionary  and thus added <code>tuple(lis)</code> as part of the key. Also, the <code>lst</code> index trick may not be as easy to implement since I am mutating <code>lst</code> through the recursion, hence why I am using <code>tuple()</code> as my keys.</p>

<p>The reasoning behind what I did is that multiple <code>lis</code> may have the same <code>[-1]</code> value. So, with this new state, the code is:</p>

<pre><code>def longest_subsequence(lst, lis=[],mem={}):
  if not lst:
    return lis
  if (tuple(lst),tuple(lis)) not in mem:
    if not lis or lst[0] &gt; lis[-1]:
      mem[(tuple(lst),tuple(lis))] = max([longest_subsequence(lst[1:], lis+[lst[0]]), longest_subsequence(lst[1:], lis)], key=len)
    else:
     mem[(tuple(lst),tuple(lis))] = longest_subsequence(lst[1:], lis)
  return mem[(tuple(lst),tuple(lis))]
</code></pre>

<p>This works for all cases I have tested so far.</p>

python algorithm dynamic-programming memoization