Longest increasing subsequence is obtained from a sequence, has elements in increasing sorted order and as long as possible. The subsequence does not necessarily have to be contiguous or unique

For example, given the array [0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15], the longest increasing subsequences is {0, 2, 6, 9, 11, 15}. It's not contiguous or unique. Other instances are {0, 2, 6, 9, 13, 15}, {0, 4, 6, 9, 11, 15, {0, 4, 6, 9, 13, 15}

Problem 1

Given an array of numbers, write an algorithm to find the length of the longest increasing subsequence in the array

Dynamic programming bottom-up/tabulation approach

Using an array to cache computed results


Time complexity: O(n2)
Space complexity: O(n)

Problem 2

Given an array of numbers, write an algorithm to find the longest increasing subsequence in the array

Dynamic programming bottom-up/tabulation approach

Using an array to cache computed results


Time complexity: O(n2)
Space complexity: O(n)

References