lis.py

import time, numpy

# [1, 2, 9, 5, 8]
# {1, 2, 3, 3, 4}
def dynamic(arr):
    size, pos = 0,  [0] * len(arr)

    for item in arr:
        start, end = 0, size

        while start != end:
            current = (start + end) // 2
            
            if pos[current] < item:
                start = current + 1
            else:
                end = current
        
        pos[start] = item
        size = max(start + 1, size)
    return size

def bfRecursive(arr, test_seq = None, pos = 0):
    if pos == len(arr):
        return test_seq
    if test_seq is None:
        test_seq = []
    
    seq_incluindo = []
    if len(test_seq) == 0 or arr[pos] > test_seq[-1]:
        seq_incluindo = bfRecursive(arr, test_seq + [arr[pos]], pos + 1)
    
    seq_excluido = bfRecursive(arr, test_seq, pos + 1)

    if len(seq_incluindo) > len(seq_excluido):
        return seq_incluindo
    else:
        return seq_excluido

def bruteForce(arr):
    return len(bfRecursive(arr))

def run(func, arr):
  start = time.time()
  
  print("Testing array: ", arr)
  print("LIS: ", func(arr))
  
  runtime = (time.time() - start) * 1000
  print("Time: %s ms" % round(runtime, 5))

def maxLisInTime(func, maxTime, starting, increasingRate):
  lastTime, lastSize = 0, starting

  while lastTime < maxTime:
    start = time.time()

    func(numpy.random.randint(-100, 100, lastSize))

    lastSize += increasingRate
    lastTime = time.time() - start

    print("Size: %s / Time: %s " % (lastSize, lastTime))

  return lastSize


arr = numpy.random.randint(-100, 100, 30)
print("Dynamic")
run(dynamic, arr)

print("\n====\n")

print("Brute force")
run(bruteForce, arr)

print("\n====\n")

print("Maxímo conjunto testável em 5 segundos:")
print("Dynamic: ", maxLisInTime(dynamic, 5, 3000000, 100000)) # 3300000 é o maior tamanho em 5 segundos (média)
# print("Brute force: ", maxLisInTime(bruteForce, 5, 50, 1)) # Muito difícil de medir