1

The ff is a code to find the longest increasing subsequence of an array/list in this case it is d. The 4th line confuses me like what does l[j][-1] mean. Let's say i=1. What would l[j][-1] be?

d = [10,300,40,43,2,69]
l = []
for i in range(len(d)):
    l.append(max([l[j] for j in range(i) if l[j][-1] < d[i]] or [[]], key=len) + [d[i]])
l4mpi
  • 5,103
  • 3
  • 34
  • 54
A.Espera
  • 21
  • 4

2 Answers2

4

When I hit something like this, I consider that either I'm facing a smart algorithm that's beyond my trivial understanding, or that I'm just seeing tight code written by somebody while their mind was well soaked with the problem at hand, and not thinking about the guy who'd try to read it later (that guy most often being the writer himself, six months later... unless he's an APL hacker...).

So I take the code and try deobfuscate it. I copy/paste it into my text editor, and from there I rework it to split complex statements or expressions into smaller ones, and to assign intermediate values to variables with meaningful names. I do so iteratively, peeling off one layer of convolution at a time, until the result makes sense to me.

I did just that for your code. I believe you'll understand it easily by yourself in this shape. And me not being all too familiar with Python, I commented a few things for my own understanding at least as much as for yours.

This resulting code could use a bit of reordering and simplification, but I left in the form that would map most easily to the original four-liner, being the direct result of its expansion. Here we go :

data = [10,300,40,43,2,69]
increasingSubsequences = []

for i in range(len(data)):

    # increasingSubsequences is a list of lists
    # increasingSubsequences[j][-1] is the last element of increasingSubsequences[j]

    candidatesForMoreIncrease = []
    for j in range(i):
        if data[i] > increasingSubsequences[j][-1]:
            candidatesForMoreIncrease.append( increasingSubsequences[j] )

    if len(candidatesForMoreIncrease) != 0:
        nonEmpty = candidatesForMoreIncrease
    else:
        nonEmpty = [[]]

    longestCandidate = max( nonEmpty, key=len )   # keep the LONGEST of the retained lists
                                         # with the empty list included as a bottom element

    # (stuff + [data[i]]) is like copying stuff and and then appending data[i] to the copy
    increasingSubsequences.append( longestCandidate + [data[i]] )



print "All increasingSubsequences : ", increasingSubsequences
print "The result you expected : ", max(increasingSubsequences, key=len)
Mathias Dolidon
  • 3,775
  • 1
  • 20
  • 28
2

This looks like python to me.

max(arg1, arg2, *args[, key])

Returns the largest item in an iterable or the largest of two or more arguments.

If one positional argument is provided, iterable must be a non-empty iterable (such as a non-empty string, tuple or list). The largest item in the iterable is returned. If two or more positional arguments are provided, the largest of the positional arguments is returned.

The optional key argument specifies a one-argument ordering function like that used for list.sort(). The key argument, if supplied, must be in keyword form (for example, max(a,b,c,key=func)).

In this case it appears the variable l = [] is going to be appended with the largest iterable or the largest of 2 arguments from the stuff inside of the max function.

iterable 1:

[l[j] for j in range(i) if l[j][-1] < d[i]]
or
[[]]

Sometimes in words it helps too:

j in l for j in range i if j in l times -1 is less than i in d or [[]]

iterable 2:

key=len

Add [d[i]] to the one that returns the max result

Append this result to l = [] making l = [result]

Append simply adds an item to the end of the list; equivalent to a[len(a):] = [x].

halfer
  • 19,824
  • 17
  • 99
  • 186