A = [*range(1000)]
for i in range(500):
    A[2*i] = random.randint(1,500)

def longest_sub_seq(arr):
    main_arr = []
    sub_arr = []
    n = len(arr)
    for ind in range(n):
        if ind < n - 1 and arr[ind] <= arr[ind+1]:
           sub_arr.append(arr[ind])
        else:
           sub_arr.append(arr[ind])
           main_arr.append(sub_arr)
           sub_arr = []
    return max(main_arr, key=len)

def longest_sub_seq(arr):
    if not arr:
        return 0
    dp = [1] * len(arr)
    for i in range(1, len(arr)):
        for j in range(0, i):
            if arr[i] > arr[j]:
                dp[i] = max(dp[i], dp[j] + 1)
    return max(dp)

def longest_increasing_subsequence_indices(seq):
    from bisect import bisect_right

    if len(seq) == 0:
        return seq

    # m[j] in iteration i is the last index of the increasing subsequence of seq[:i]
    # that ends with the lowest possible value while having length j
    m = [None] * len(seq)
    predecessor = [None] * len(seq)
    best_len = 0

    for i, item in enumerate(seq):
        j = bisect_right([seq[k] for k in m[:best_len]], item)
        m[j] = i
        predecessor[i] = m[j-1] if j > 0 else None

This should run in O(1) right excludin the array copy:
```
def ls(seq):
   lo=0
   hi=0
   ma=[]
   pre=seq[0]
   for b,i in enumerate(seq):
       if i>pre:
           lo=b
       elif i<pre:
           hi=b
       ma=max(ma,seq[min(lo,hi):b],key=len)
       pre=i
   return ma

```