"""
 long_increasing_sequence.py

 Jim Mahoney | April 1 2019 | cs.marlboro.college | MIT License
"""
# No, this isn't an April Fool joke. :)
#
# The problem is this one :
# https://en.wikipedia.org/wiki/Longest_increasing_subsequence
#
# The notation I'll use is :
#
#   n              count of numbers in the sequence
#   seq[i]         the sequence numbers, i = 0 ... (n-1)
#   longest[i]     the length of the longest sequence which
#                  includes seq[i] and any of { seq[0], seq[1], ... seq[i-1 }
#   i_prev[i]      the index of the previous term in the longest[i] sequence,
#                  None if there is no previous term.
#
# So for example if
#
#   seq     = [0, 8, 4, 12, 2, 10, 6, 14, 1, 9,  5, 13,  3, 11,  7, 15]  numbers
#   i       = [0, 1, 2,  3, 4,  5, 6,  7, 8, 9, 10, 11, 12, 13, 14, 15]  indices
#
# then
#
#   n       = 16
#   longest = [1,          #  0                    must end with seq[0]=0
#              2,          #  0, 8                 must end with seq[1]=8
#              2,          #  0, 4                 must end with seq[2]=4
#              3,          #  0, 4, 12             must end with seq[3]=12
#              2,          #  0, 2                 must end with seq[4]=2
#              3,          #  0, 4, 10             must end with seq[4]=10
#              ... ]
#
#  i_prev   = [None,      # 0 ; 
#              0,         # 0, 8;        element before  8 is 0 at seq[0]
#              0,         # 0, 4;        element before  4 is 0 at seq[0]
#              2,         # 0, 4, 12;    element before 12 is 4 at seq[2]
#              ... ]
#
#  Once we have these arrays, the answer is max(longest).
#  We can find a (not unique) sequence of this length
#  by tracing back through the i_prev entries.
#
# The recursion relation for the longest[] array is
#
#    longest[0] = 1
#    longest[i] = max( 1+longest[j] where j < i and seq[j] < seq[i] )
#                 or 1 if there is no seq[j] < seq[i]
#
# which is a loop-within-a-loop that gives O(n**2) for the calculation.
#
# (It is possible to do better, namely O(n log(n)), by eliminating those
# sequences which are always worse than the others, as mentioned in
# the wikipedia article. But here I'm just taking the simplest approach.)
#
# We can initialize longest[] to 1 and i_prev to None,
# then update i_prev to j whenever longest[i] changes in
# the loop where we look for max().

DEBUG = False

def longest_increasing_sequence(seq):
    """ Return longest increasting sub-sequence of seq[] 
        >>> longest_increasing_sequence([3, 2, 1])
        [3]
        >>> longest_increasing_sequence([3, 2, 4, 1])
        [3, 4]
        >>> longest_increasing_sequence([1, 2, 3])
        [1, 2, 3]
        >>> longest_increasing_sequence([50, 1, 10, 2, 20, 3, 4, 2])
        [1, 2, 3, 4]
        >>> longest_increasing_sequence([50, 1, 10, 2, 20, 3, 4, 2])
        [1, 2, 3, 4]
        >>> longest_increasing_sequence([10, 2, 1, 4, 17, 9, 6, 12, 8, 1, 10])
        [2, 4, 6, 8, 10]
        >>> wikipedia = [0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15]
        >>> longest_increasing_sequence(wikipedia) # length 6; not unique
        [0, 4, 6, 9, 13, 15]
    """
    # Initialize data structures
    n = len(seq)
    i_prev = [None] * n
    longest = [1] * n
    # Find each longest[i] and i_prev[i] by looping over i, then j < i.
    # Apply the recursion rule at each step.
    for i in range(n):
        for j in range(i):
            if seq[j] < seq[i] and longest[j] + 1 > longest[i]:   # REUCURSION
                longest[i] = longest[j] + 1                       # RULE
                i_prev[i] = j                                     #
    # Here is our data tableau - from this we find the answer.
    if DEBUG:
        print("seq : ", seq)
        print("longest : ", longest)
        print("i_prev : ", i_prev)
    # Now find the best sub-sequence by getting the max of longest[i].
    i_best = 0         # last index of best sub-sequence.
    for i in range(n):
        if longest[i] > longest[i_best]:
            i_best = i
    # Finally, reconstruct a longest sequence by tracing back through i_prev.
    n_result = longest[i_best]          # length of longest sub-sequence
    result = [None] * n_result          # allocate space for result
    i = i_best                          # index of last entry in longest seq
    i_result = n_result - 1             # where to put that in result
    while i_result >= 0:
        if DEBUG:
            print("i={}, i_result={}, result={}".format(i, i_result, result))
        result[i_result] = seq[i]
        i = i_prev[i]
        i_result -= 1
    return result

if __name__ == '__main__':
    import doctest
    doctest.testmod()