Longest Increasing Subsequence

The Idea

Scan left to right. For each element, look back at every earlier element that is smaller and ask which chain it can extend, keeping the longest one found. The answer is the largest value anywhere in that table, not the final cell, because the best chain may end in the middle. Elements are never reordered.

Real-World Example

A cycling coach reads one season of training logs in date order and pulls out the longest run of rides — skipping as many as needed — where each kept ride was faster than the one kept before it. The dates stay fixed; that fixed order is what makes it evidence of progress.

The Code

def lis(nums):
    best = [1] * len(nums)              # best[i] = longest chain ending at i
    for i in range(len(nums)):
        for j in range(i):
            if nums[j] < nums[i]:       # nums[i] can extend the chain ending at j
                best[i] = max(best[i], best[j] + 1)
    return max(best) if best else 0

print(lis([10, 9, 2, 5, 3, 7, 101, 18]))   # 4
print(lis([7, 7, 7]))                      # 1

def lis(nums):
  best = [1] * len(nums)
  for i in range(len(nums)):
      for j in range(i):
          if ___:
              best[i] = max(best[i], best[j] + 1)
  return max(best)

print(lis([3, 1, 4, 2, 5]))   # should print 3