# Longest Increasing Subsequence, Leetcode, Dynamic programming

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

Example:

Input: `[10,9,2,5,3,7,101,18`

Output: 4

Explanation: The longest increasing subsequence is `[2,3,7,101]`, therefore the length is `4`.

Note:

• 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?

Solution –

Let us just think about this question and make sure that we understand this. Longest increasing subsequence is the maximum count of numbers which are in increasing order in an array. We can skip some numbers in between but we can not change the order of the numbers.

For example- for a smaller array like [1, 2, 3, 4] longest common subsequence is 4 and for [1, 2, 4, 3] it is 3.

So for every case of input[i], the result is input[j] +1 if i > j and input[i] > input [j] otherwise 1 if input[i] <= input [j]

It is a case of overlapping subproblems. as for every i we have to calculate for i-1 and for every i-1 we have to calculate for i-2.

We can start  thinking about the code.

1. By default we know that for each one digit, longest common subsequence is 1. So initially we can create and array with same length as input and put 1 on each index.
2. we can have two nested loops, one of i from 1 to n-1 and j from 0 to i-1.
3. input is nums in our case. If nums[i] > nums[j] and helper[j]+1 > helper[i] then set helper[i] = helper[j]
4. otherwise we don’t need to update helper[i] as it already has subsequence from lower indexes.
5. In the end, return max value from the helper array.

Code is implemented in JavaScript but it will be same in other languages.