def lds(sequence, numbers, max_sequence):
    """
    In the following demo, I have chosen for clarity not to use a deque,
    which supports efficient appending and removing of values to either
    the front or back of the list. Instead, I am just using regular
    lists.
 
    The important thing to note is that this function is never called
    with the values for the sequence and numbers arguments repeated
    implying that there are no overlapping subproblems,
    which is the requirements for a dynamic programming approach.
    With true dynamic programming you have memoization to remember a prior
    subproblem result for when that subproblem arises again. But that
    never happens here.
 
    Instead, as you iterate the input numbers you arrive at one of 3
    conditions: (1) The current input number can not be appended nor prepended and you
    have found the longest descending sequence (lds) for the descisions made up
    to this point or (2) The number is appended or prepended as appropriate and you
    continue iterating or (3) The number is not added to the sequence and you continue
    iterating. When the current number can be added to the sequence, you perform options
    2 and 3 and see which one producers a longer lds.
    """
 
    print(f'sequence, arguments -> {sequence}, {numbers}') # Print out the arguments
 
    if len(sequence) == 0:
        n = numbers[0]
        numbers = numbers[1:] # New list without the first element
        sequence = [n]
        max_sequence = sequence
        return lds(sequence, numbers, max_sequence)
 
    if not numbers:
        l = len(sequence)
        if len(sequence) > len(max_sequence):
            max_sequence = sequence
        return max_sequence
 
    n = numbers[0]
    # Can we prepend or append?
    if n <= sequence[0] and n >= sequence[-1]:
        # No!
        l = len(sequence)
        if l > len(max_sequence):
            max_sequence = sequence
        return max_sequence
 
    numbers = numbers[1:] # New list without the first number
    # Compute maximum length without appending/prepending:
    max_sequence_1 = lds(sequence, numbers, max_sequence)
    l1 = len(max_sequence_1)
    # Compute maximum length with appending/prepending:
    if n > sequence[0]:
        sequence = [n, *sequence] # Prepend
    else:
        sequence = [*sequence, n] # Append
    max_sequence_2 = lds(sequence, numbers, max_sequence)
    l2 = len(max_sequence_2)
 
    return max_sequence_1 if l1 >= l2 else max_sequence_2
 
max_sequence = lds([], [6, 7, 3, 5, 4], [])
print('lds: ', max_sequence)
 

ZGVmIGxkcyhzZXF1ZW5jZSwgbnVtYmVycywgbWF4X3NlcXVlbmNlKToKICAgICIiIgogICAgSW4gdGhlIGZvbGxvd2luZyBkZW1vLCBJIGhhdmUgY2hvc2VuIGZvciBjbGFyaXR5IG5vdCB0byB1c2UgYSBkZXF1ZSwKICAgIHdoaWNoIHN1cHBvcnRzIGVmZmljaWVudCBhcHBlbmRpbmcgYW5kIHJlbW92aW5nIG9mIHZhbHVlcyB0byBlaXRoZXIKICAgIHRoZSBmcm9udCBvciBiYWNrIG9mIHRoZSBsaXN0LiBJbnN0ZWFkLCBJIGFtIGp1c3QgdXNpbmcgcmVndWxhcgogICAgbGlzdHMuCgogICAgVGhlIGltcG9ydGFudCB0aGluZyB0byBub3RlIGlzIHRoYXQgdGhpcyBmdW5jdGlvbiBpcyBuZXZlciBjYWxsZWQKICAgIHdpdGggdGhlIHZhbHVlcyBmb3IgdGhlIHNlcXVlbmNlIGFuZCBudW1iZXJzIGFyZ3VtZW50cyByZXBlYXRlZAogICAgaW1wbHlpbmcgdGhhdCB0aGVyZSBhcmUgbm8gb3ZlcmxhcHBpbmcgc3VicHJvYmxlbXMsCiAgICB3aGljaCBpcyB0aGUgcmVxdWlyZW1lbnRzIGZvciBhIGR5bmFtaWMgcHJvZ3JhbW1pbmcgYXBwcm9hY2guCiAgICBXaXRoIHRydWUgZHluYW1pYyBwcm9ncmFtbWluZyB5b3UgaGF2ZSBtZW1vaXphdGlvbiB0byByZW1lbWJlciBhIHByaW9yCiAgICBzdWJwcm9ibGVtIHJlc3VsdCBmb3Igd2hlbiB0aGF0IHN1YnByb2JsZW0gYXJpc2VzIGFnYWluLiBCdXQgdGhhdAogICAgbmV2ZXIgaGFwcGVucyBoZXJlLgoKICAgIEluc3RlYWQsIGFzIHlvdSBpdGVyYXRlIHRoZSBpbnB1dCBudW1iZXJzIHlvdSBhcnJpdmUgYXQgb25lIG9mIDMKICAgIGNvbmRpdGlvbnM6ICgxKSBUaGUgY3VycmVudCBpbnB1dCBudW1iZXIgY2FuIG5vdCBiZSBhcHBlbmRlZCBub3IgcHJlcGVuZGVkIGFuZCB5b3UKICAgIGhhdmUgZm91bmQgdGhlIGxvbmdlc3QgZGVzY2VuZGluZyBzZXF1ZW5jZSAobGRzKSBmb3IgdGhlIGRlc2Npc2lvbnMgbWFkZSB1cAogICAgdG8gdGhpcyBwb2ludCBvciAoMikgVGhlIG51bWJlciBpcyBhcHBlbmRlZCBvciBwcmVwZW5kZWQgYXMgYXBwcm9wcmlhdGUgYW5kIHlvdQogICAgY29udGludWUgaXRlcmF0aW5nIG9yICgzKSBUaGUgbnVtYmVyIGlzIG5vdCBhZGRlZCB0byB0aGUgc2VxdWVuY2UgYW5kIHlvdSBjb250aW51ZQogICAgaXRlcmF0aW5nLiBXaGVuIHRoZSBjdXJyZW50IG51bWJlciBjYW4gYmUgYWRkZWQgdG8gdGhlIHNlcXVlbmNlLCB5b3UgcGVyZm9ybSBvcHRpb25zCiAgICAyIGFuZCAzIGFuZCBzZWUgd2hpY2ggb25lIHByb2R1Y2VycyBhIGxvbmdlciBsZHMuCiAgICAiIiIKCiAgICBwcmludChmJ3NlcXVlbmNlLCBhcmd1bWVudHMgLT4ge3NlcXVlbmNlfSwge251bWJlcnN9JykgIyBQcmludCBvdXQgdGhlIGFyZ3VtZW50cwoKICAgIGlmIGxlbihzZXF1ZW5jZSkgPT0gMDoKICAgICAgICBuID0gbnVtYmVyc1swXQogICAgICAgIG51bWJlcnMgPSBudW1iZXJzWzE6XSAjIE5ldyBsaXN0IHdpdGhvdXQgdGhlIGZpcnN0IGVsZW1lbnQKICAgICAgICBzZXF1ZW5jZSA9IFtuXQogICAgICAgIG1heF9zZXF1ZW5jZSA9IHNlcXVlbmNlCiAgICAgICAgcmV0dXJuIGxkcyhzZXF1ZW5jZSwgbnVtYmVycywgbWF4X3NlcXVlbmNlKQoKICAgIGlmIG5vdCBudW1iZXJzOgogICAgICAgIGwgPSBsZW4oc2VxdWVuY2UpCiAgICAgICAgaWYgbGVuKHNlcXVlbmNlKSA+IGxlbihtYXhfc2VxdWVuY2UpOgogICAgICAgICAgICBtYXhfc2VxdWVuY2UgPSBzZXF1ZW5jZQogICAgICAgIHJldHVybiBtYXhfc2VxdWVuY2UKCiAgICBuID0gbnVtYmVyc1swXQogICAgIyBDYW4gd2UgcHJlcGVuZCBvciBhcHBlbmQ/CiAgICBpZiBuIDw9IHNlcXVlbmNlWzBdIGFuZCBuID49IHNlcXVlbmNlWy0xXToKICAgICAgICAjIE5vIQogICAgICAgIGwgPSBsZW4oc2VxdWVuY2UpCiAgICAgICAgaWYgbCA+IGxlbihtYXhfc2VxdWVuY2UpOgogICAgICAgICAgICBtYXhfc2VxdWVuY2UgPSBzZXF1ZW5jZQogICAgICAgIHJldHVybiBtYXhfc2VxdWVuY2UKCiAgICBudW1iZXJzID0gbnVtYmVyc1sxOl0gIyBOZXcgbGlzdCB3aXRob3V0IHRoZSBmaXJzdCBudW1iZXIKICAgICMgQ29tcHV0ZSBtYXhpbXVtIGxlbmd0aCB3aXRob3V0IGFwcGVuZGluZy9wcmVwZW5kaW5nOgogICAgbWF4X3NlcXVlbmNlXzEgPSBsZHMoc2VxdWVuY2UsIG51bWJlcnMsIG1heF9zZXF1ZW5jZSkKICAgIGwxID0gbGVuKG1heF9zZXF1ZW5jZV8xKQogICAgIyBDb21wdXRlIG1heGltdW0gbGVuZ3RoIHdpdGggYXBwZW5kaW5nL3ByZXBlbmRpbmc6CiAgICBpZiBuID4gc2VxdWVuY2VbMF06CiAgICAgICAgc2VxdWVuY2UgPSBbbiwgKnNlcXVlbmNlXSAjIFByZXBlbmQKICAgIGVsc2U6CiAgICAgICAgc2VxdWVuY2UgPSBbKnNlcXVlbmNlLCBuXSAjIEFwcGVuZAogICAgbWF4X3NlcXVlbmNlXzIgPSBsZHMoc2VxdWVuY2UsIG51bWJlcnMsIG1heF9zZXF1ZW5jZSkKICAgIGwyID0gbGVuKG1heF9zZXF1ZW5jZV8yKQoKICAgIHJldHVybiBtYXhfc2VxdWVuY2VfMSBpZiBsMSA+PSBsMiBlbHNlIG1heF9zZXF1ZW5jZV8yCgptYXhfc2VxdWVuY2UgPSBsZHMoW10sIFs2LCA3LCAzLCA1LCA0XSwgW10pCnByaW50KCdsZHM6ICcsIG1heF9zZXF1ZW5jZSkK