## 300. Longest Increasing Subsequence

Given an unsorted array of integers, find the length of longest increasing subsequence.

For example,
Given [10, 9, 2, 5, 3, 7, 101, 18],
The longest increasing subsequence is [2, 3, 7, 101], therefore the length is 4. Note that there may be more than one LIS combination, it is only necessary for you to return the length.

Your algorithm should run in O(n2) complexity.

Follow up: Could you improve it to O(n log n) time complexity?

Credits:
Special thanks to @pbrother for adding this problem and creating all test cases.

b'
\n\n

## Solution

\n
\n

#### Approach #1 Brute Force [Time Limit Exceeded]

\n

Algorithm

\n

The simplest approach is to try to find all increasing subsequences and then returning the maximum length of longest increasing subsequence. In order to\ndo this, we make use of a recursive function which returns the length of the LIS possible from the current element(corresponding to )\n onwards(including the current element). Inside each function call, we consider two cases:

\n
\n
1. \n

The current element is larger than the previous element included in the LIS. In this case, we can include the current element in the LIS. Thus, we find out the\nlength of the LIS obtained by including it. Further, we also find out the length of LIS possible by not including the current element in the LIS. The value returned\nby the current function call is, thus, the maximum out of the two lengths.

\n
2. \n
3. \n

The current element is smaller than the previous element included in the LIS. In this case, we can\'t include the current element in the LIS. Thus, we find out only\nthe length of the LIS possible by not including the current element in the LIS, which is returned by the current function call.

\n
4. \n
\n\n

Complexity Analysis

\n
\n
• \n

Time complexity : . Size of recursion tree will be .

\n
• \n
• \n

Space complexity : . array of size is used.

\n
• \n
\n
\n

#### Approach #2 Recursion with memorization [Memory Limit Exceeded]

\n

Algorithm

\n

In the previous approach, many recursive calls had to made again and again with the same parameters. This redundancy can be eliminated by storing the results obtained for\na particular call in a 2-d memorization array . represents the length of the LIS possible using as the previous element considered to\nbe included/not included in the LIS, with as the current element considered to be included/not included in the LIS. Here, represents the given array.

\n\n

Complexity Analysis

\n
\n
• \n

Time complexity : . Size of recursion tree can go upto .

\n
• \n
• \n

Space complexity : . array of is used.

\n
• \n
\n
\n

#### Approach #3 Dynamic Programming [Accepted]

\n

Algorithm

\n

This method relies on the fact that the longest increasing subsequence possible upto the index in a given array is independent of the elements coming\nlater on in the array. Thus, if we know the length of the LIS upto index, we can figure out the length of the LIS possible by including the element\nbased on the elements with indices such that .

\n

We make use of a array to store the required data. represents the length of the longest increasing subsequence possible considering the array elements upto the \nindex only ,by necessarily including the element. In order to find out , we need to try to append the current element() in every possible increasing subsequences upto the \nindex(including the index), such that the new sequence formed by adding the current element is also an increasing subsequence. Thus, we can easily determine\n using:

\n

\n\n

\n

At the end, the maximum out of all the \'s to determine the final result.

\n

\n\n

\n

The following animation illustrates the method:

\n\n

!?!../Documents/300_LIS.json:1000,563!?!

\n\n

Complexity Analysis

\n
\n
• \n

Time complexity : . Two loops of are there.

\n
• \n
• \n

Space complexity : . array of size is used.

\n
• \n
\n
\n

#### Approach #4 Dynamic Programming with Binary Search[Accepted]:

\n

Algorithm

\n

In this approach, we scan the array from left to right. We also make use of a array initialized with all 0\'s. This array is meant to store the\nincreasing subsequence formed by including the currently encountered element.\n While traversing the array, we keep on filling the array with\nthe elements encountered so far. For the element corresponding to the index (),\n we determine its correct position in the array(say index) by making use of Binary Search(which can be used since the\n array is storing increasing subsequence) and also insert it at the correct position. An important point to be noted is that for Binary Search, we consider\n only that portion of the array in which we have made the updations by inserting some elements at their correct positions(which remains always sorted).\n Thus, only the elements upto the index\n in the array can determine the position of the current element in it.\n Since, the element enters its correct position() in an ascending order in the array, the\n subsequence formed so far in it is surely an increasing subsequence. Whenever this position index becomes equal to the length of the LIS formed so far(),\n it means, we need to update the as .

\n

Note: array does not result in longest increasing subsequence, but length of array will give you length of LIS.

\n

Consider the example:

\n

input: [0, 8, 4, 12, 2]

\n

dp: 

\n

dp: [0, 8]

\n

dp: [0, 4]

\n

dp: [0, 4, 12]

\n

dp: [0 , 2, 12] which is not the longest increasing subsequence, but length of array results in length of Longest Increasing Subsequence.

\n\n

Note: Arrays.binarySearch() method returns index of the search key, if it is contained in the array, else it returns (-(insertion point) - 1). The insertion point is the point at which the key would be inserted into the array: the index of the first element greater than the key, or a.length if all elements in the array are less than the specified key.

\n

Complexity Analysis

\n
\n
• \n

Time complexity : . Binary search takes time and it is called times.

\n
• \n
• \n

Space complexity : . array of size is used.

\n
• \n
\n
\n

Analysis written by: @vinod23

\n
'