Given an array of size n, find the length of the longest increasing subsequence (LIS), in which the elements of the subsequence are sorted in increasing order.

Hint

Assume the list already ends with the largest number. For each number in the list (from the beginning), if the current number is smaller than the last number in the list, recursively count the increasing subsequences in the sublist up to the current number's position. Return the maximum count found during the recursion.

Since the list might not always end with the largest number, create all possible sublists of the original list (from the beginning to different ending positions). For each sublist, apply the logic from step 1 to find the count of increasing subsequences. Select and return the maximum count found among all the sublists.

# Python implementation

def count(ls):
  last = len(ls) - 1

  if last == 0:
    return 1
  
  mx = 1
  
  for i in range(last):
    if ls[i] < ls[last]:
      mx = max(mx, 1 + count(ls[0:i + 1]))

  return mx

ls = [3, 10, 2, 1, 20]

mx = 1

for i in range(len(ls)):
  mx = max(mx, count(ls[0:i + 1]))

print(mx)

// Javascript implementation

function count(list) {
  const last = list.length - 1;

  if (last == 0) {
    return 1;
  }
  
  let max = 1;
  
  for (let i = 0; i < last; i++) {
    if (list[i] < list[last]) {
      max = Math.max(max, 1 + count(list.slice(0, i + 1)));
    }
  }

  return max;
}

const list = [3, 10, 2, 1, 20];

let max = 1;

for (let i = 0; i < list.length; i++) {
  max = Math.max(max, count(list.slice(0, i + 1)));
}

console.log(max);

Find longest increasing subsequence (LIS)

Hint