How to find longest increasing subsequence

Given an array of integers, find the length of the longest increasing subsequence (LIS)

 

Example 1

Input: [3, 2, 9, 4, 10, 11, 7]

Output: 4

Explanation: [3, 9, 10, 11] or [2, 9, 10, 11]

Example 2

Input: [3, 2, 1]

Output: 1

The first step in solving any problem is understanding what the problem is. We need to understand the problem's description and what needs to be solved. In this case, before starting to think about possible solutions, we need to know what is a subsequence

A subsequence of a given sequence is a sequence that can be derived from the given sequence by removing some or no elements without changing the order of the remaining elements.

Now we know what is a subsequence. In the problem, we need to find not any subsequence, we need to find the length of the longest subsequence, and this subsequence should be an increasing subsequence. The longest subsequence is a subsequence with maximum possible elements. The increasing subsequence is a subsequence where each next element in the subsequence is greater than the previous one.

Now we know what the longest increasing subsequence is. It's a subsequence where each element is greater than the previous one, and this subsequence has the maximum possible elements. To solve the problem, we are going to use dynamic programming. The idea behind dynamic programming is pretty straightforward, is to split the initial problem into subproblems, solve all subproblems, and in the end, combine subproblems solutions into a solution. Let's see how we can use this approach to solve our problem.

For instance, we have an input array 3, 1, 5, 0, and we need to find the longest increasing subsequence.

The first step we need to do is to split the problem into subproblems. Our input array has four elements. What if the array will have only one element. In this case, the longest increasing subsequence contains only one element. In other words, we already know how to solve a problem if an input array has only one element.

What if an input array has two elements? We already know the input array has two subsequences with lengths 1, and we need to find out. Is it possible to create an increasing subsequence with length 2. To answer this question, we need to compare the second element with the first one.

• if the second element is greater than the first one, we found an increasing subsequence with length 2
• if the second element is less than the first one, we did not find a new increasing subsequence

In our case, 1 is less than 3, and we still have the longest increasing subsequence with the length of 1. The next example is when the input array has tree elements.

In this step, we already know the longest increasing subsequence for the array 3, 1 and need to know - is it possible to get the longest increasing subsequence by adding 5 to already existing subsequences?

• 5 is greater than 1 => we got a new the longest increasing subsequence 1, 5
• 5 is greater than 3 => we got one more the longest increasing subsequence 3, 5

and finally, the scenario with four elements.

We already know the longest increasing subsequence for the array 3, 1, 5, and to know the final result, we need to try to add 0 to the already existing subsequences. 0 is less than 3, 1 and 5, i.e., it is impossible to create a new longest increasing subsequence by adding 0 to the already existing subsequences. So 3, 1, 5, 0 has two longest increasing subsequences: 3, 5 and 1, 5.

The generic approach to finding the longest increasing subsequence is:

• sequence with length 1 has only one longest increasing subsequences
• compare i element with all i - 1 elements, and if
  • array[i] > array[j], the new longest increasing subsequence will length Max(lis[i], lis[j])

Code

        public int LongestIncreasingSubsequence(int[] array)
        {
            if (array == null || array.Length == 0)
            {
                return 0;
            }

            if (array.Length == 1)
            {
                return 1;
            }

            int result = 0;
            int[] cache = new int[array.Length];

            for (int i = 0; i < array.Length; i++)
            {
                cache[i] = 1;

                for (int j = i - 1; j >= 0; j--)
                {
                    if (array[i] > array[j])
                    {
                        cache[i] = Math.Max(cache[j] + 1, cache[i]);
                    }
                }

                result = Math.Max(result, cache[i]);
            }

            return result;
        }

The time complexity is O(n^2).