Longest Sequential Subarray

2022-02-21.py

question = """

Given an array of integers, find the length of the longest sub-sequence such that elements 
in the sub-sequence are consecutive integers, the consecutive numbers can be in any order.

Example:

$ longestSubSeq([1, 9, 87, 3, 10, 4, 20, 2, 45])
$ 4 // 1, 3, 4, 2

$ longestSubSeq([36, 41, 56, 35, 91, 33, 34, 92, 43, 37, 42])
$ 5 // 36, 35, 33, 34, 37


"""

def longestSubSeq(array):
    array_pos = []
    for i in range(len(array)):
        el_pos = [array[i], i]
        array_pos.append(el_pos)
    sorted_array_pos = sorted(array_pos, key=lambda x: x[0])
    candidates = []
    candidate = []
    for i in range(len(sorted_array_pos)-1):
        candidate.append(sorted_array_pos[i])
        if sorted_array_pos[i+1][0] > sorted_array_pos[i][0] + 1:
            candidates.append(candidate)
            candidate = []
    candidates.append(candidate)
    sorted_candidates = sorted(candidates, key=lambda x: len(x))
    longestSubSeqLen = len(sorted_candidates[-1])
    restored_el_pos = sorted(sorted_candidates[-1], key=lambda x: x[1])
    restored_els = []
    for el_pos in restored_el_pos:
        el, pos = el_pos
        restored_els.append(str(el))
    response = str(longestSubSeqLen) + " // " + ", ".join(restored_els)
    print(response)
  
longestSubSeq([1, 9, 87, 3, 10, 4, 20, 2, 45])
longestSubSeq([36, 41, 56, 35, 91, 33, 34, 92, 43, 37, 42])