anduril_longest_sub_sequence_non_contiguose.py

# 1 2 3 -> 3
# 1 2 8 6 7 -> 4
#  1 2 6 7

# 1 2 -99 3 -97 -96 -95 4 5 => 4 

#  1: 1
#  2: 2
#  -99: 1
#  3: 3
#  -97: 2
#  -96: 3
#  -96: 4
 

 

# def addNumbers(a,b):
#     sum = a + b
#     return sum

# num1 = int(input())
# num2 = int(input())

# print("The sum is", addNumbers(num1, num2))


from typing import List

LastNumberInSequence = int
Length = int

def length_increasing_sub(x: List[int]) -> int:
    acc: Dict[LastNumberInSequence, Length] = {}
    for current_number in x:
        is_placed = False
        for number in [key for key in acc]: # <= [key for key in acc] new value X
            if current_number > number:
                is_placed = True
                if current_number not in acc:
                    acc[current_number] = acc[number] + 1
                else:
                    acc[current_number] = max(acc[current_number], acc[number] + 1)
        if not is_placed:
            acc[current_number] = 1
    return max([length for _, length in acc.items()])

        

print(length_increasing_sub([1,2,-99,3, -98, -97, -96]))