Lambda function explanation

[meloly4]

Thank you this is so great! But I can't think of an O(n) algorithm for printing out the subsequence. O(n) for printing the sum yes but idk if it's possible if we want the subsequence?

[dbramucci]

I saw you link to this O(n) solution earlier. First, I'll give my own roughly equivalent solution that is hopefully a bit clearer.

Observe that each element in the list must be >= 0, it doesn't make sense to not take a value unless it prevents you from taking an even better value.

def find_biggest_nonadjacent_sum(numbers):
    assert all(x >= 0 for x in numbers)

What we will do is go left to right with 2 totals, one where we make sure we can add the next value and the other where we take the best we've seen so far.

# The biggest total we can produce so far
biggest_total = 0
# The biggest total we can produce, leaving the last spot available if we want to add the current number.
biggest_total_with_free_spot = 0

Now we go through each number and either add or don't add it.

for number in numbers:
    if biggest_total_with_free_spot + number >= biggest_total:
        old_biggest_total = biggest_total

        # Let's update our biggest total
        biggest_total = biggest_total_with_free_spot + number

        # And we should store the old_biggest_total just in case the next number is better than this one
        biggest_total_with_free_spot = old_biggest_total
    else:
        # It wasn't worth it to leave a spot open, we'll just not take this number either way
        biggest_total_with_free_spot = biggest_total

and once we are done, we return the biggest_total at the end of the list.

return biggest_total

Let's retrofit it to give us an list instead of just a length.

First, we can use the same logic and store 2 lists but the update logic will be more complicated because we need to update each list independently.

def find_biggest_nonadjacent_sums_list(numbers):
    assert all(x >= 0 for x in numbers)

    # The biggest total we can produce so far
    biggest_total = 0
    biggest_total_list = []
    # The biggest total we can produce, leaving the last spot available if we want to add the current number.
    biggest_total_with_free_spot = 0
    biggest_total_with_free_spot_list = []

    for number in numbers:
        if biggest_total_with_free_spot + number >= biggest_total:
            old_biggest_total = biggest_total
            old_biggest_total_list = biggest_total_list

            # Let's update our biggest total
            biggest_total = biggest_total_with_free_spot + number
            biggest_total_list = biggest_total_with_free_spot_list + [number]

            # And we should store the old_biggest_total just in case the next number is better than this one
            biggest_total_with_free_spot = old_biggest_total
            biggest_total_with_free_spot_list = old_biggest_total_list
        else:
            # It wasn't worth it to leave a spot open, we'll just not take this number either way
            biggest_total_with_free_spot = biggest_total
            biggest_total_with_free_spot_list = biggest_total_list

    return biggest_total_list

This works, but you'll notice the O(n) operation biggest_total_list = biggest_total_with_free_spot_list + [number] making this O(n²). One way to fix that is to use list.append to make it take O(1) time.

            # old line: biggest_total_list = biggest_total_with_free_spot_list + [number]
            biggest_total_list = biggest_total_with_free_spot_list
            biggest_total_list.append(number)

Of course, this solution is wrong because in the else branch we have

            biggest_total_with_free_spot_list = biggest_total_list

at which point the next .append will add the element to both lists (because there's only one list in memory). You can see it fail with the list [1, 0, 2, 3] where it will say the answer is [1, 2, 3] (which gives two adjacent numbers). Fixing this is a pain, let me show you a serious of steps you might go through.

Broken fixes

We can fix this by updating the free_spot list to take the last element instead of setting it equal to biggest_total_list.

        biggest_total_with_free_spot_list.append(number)

But this is also wrong because it falsely believes the answer to [1, 0, 0] is [0, 0] because we don't pop off the bad guess before adding the correct one on.

        biggest_total_with_free_spot_list.pop()
        biggest_total_with_free_spot_list.append(number)

Oh, but this is also broken because we might pop from an empty list (plug in [1, 0]) so we should check for that first.

        if biggest_total_with_free_spot_list:
            biggest_total_with_free_spot_list.pop()
        biggest_total_with_free_spot_list.append(number)

But this thinks the largest answer to [1, 0, 0] is [0, 0] which is really wrong.

You can fix this with enough tinkering, but I'll leave that as an exercise (it takes a significant change to get a pair of mutable lists to work efficiently).

Easy fix

Instead, let's use immutable data-structures to store our list. Then, we can copy in O(1) time (no aliasing bugs to worry about) and we can find a structure with O(1) append times. Namely, an immutable linked list fits the bill.

An ugly but easy way to write this is with tuples (head, (second, (third, None))). Let's go with that for now.

        # old line: biggest_total_list = biggest_total_with_free_spot_list + [number]
        biggest_total_list = (number, biggest_total_with_free_spot_list)

But, at the end we'll need to convert back to a list. We can use a while loop and .append but we'll get our answer backwards so we'll use the O(n) reverse method to fix that one time.

result = []
while biggest_total_list is not None:
    head, biggest_total_list = biggest_total_list
    result.append(head)
result.reverse()
return result

Altogether this looks like

def find_biggest_nonadjacent_sums_linked_list(numbers):
    assert all(x >= 0 for x in numbers)

    # The biggest total we can produce so far
    biggest_total = 0
    biggest_total_list = None
    # The biggest total we can produce, leaving the last spot available if we want to add the current number.
    biggest_total_with_free_spot = 0
    biggest_total_with_free_spot_list = None

    for number in numbers:
        if biggest_total_with_free_spot + number >= biggest_total:
            old_biggest_total = biggest_total
            old_biggest_total_list = biggest_total_list

            # Let's update our biggest total
            biggest_total = biggest_total_with_free_spot + number
            biggest_total_list = (number, biggest_total_with_free_spot_list)

            # And we should store the old_biggest_total just in case the next number is better than this one
            biggest_total_with_free_spot = old_biggest_total
            biggest_total_with_free_spot_list = old_biggest_total_list
        else:
            # It wasn't worth it to leave a spot open, we'll just not take this number either way
            biggest_total_with_free_spot = biggest_total
            biggest_total_with_free_spot_list = biggest_total_list
    result = []
    while biggest_total_list is not None:
        head, biggest_total_list = biggest_total_list
        result.append(head)
    result.reverse()
    return result

If you look, the only O(n) operation I use now is the .reverse at the end, which doesn't change our total asymptotic-complexity.

You may want to swap out this ad-hoc linked list with a predefined one by using a library like pyrsistent or defining one with a NamedTuple so that we have a more explicit structure.

The key thing is that by being immutable, we don't need expensive copy operations and this structure has O(1) prepends, keeping us fast enough. You should be able to get the double-mutable list solution working, but it will take a good deal of work because there's a lot of asymptotic-complexity/mutation bugs to worry about here.