# Longest increasing subsequence problem

Given an array of integers, find the largest sub sequence such that if i<j then a[i] <a[j].

For example, in array {2,4,6,3,5,7,9} longest increasing sub sequence is of length 5 {2,4,6,7,9}

### Analysis

Here idea is to find out if the

**longest subsequence**already present before a particular element can include this element and remains increasing after adding this element. This can be easily done by checking every element from start of the array to element under consideration, if element*i*is less than current element, then current element can be part of the sub sequence ending with element*i*. So length of longest increasing sub sequence can be**(length of sub sequence ending at i )+1.**We would check for each such element and take the maximum length.

Let’s work on an example.

A = {2,4,6,3,5,7,9}

Now we initialize len[0] =1, that means there is an increasing sub sequence of length 1 at index 0.

for i =1 i.e 4, we will check 0 to 1. We start with 0, a[0] < a[1], hence LIS length is 2 (LIS[0] +1).

For i =2, i.e. 6 we check 0 to 2. We check that LIS[0] =1 and LIS[1] =2. We can have a sub sequence ending a[1] and adding a[2]. Hence max LIS is 3 till index 2. Hence LIS[2] = 3 (LIS[1] +1).

For i =3 i.e 3, we check from 0 to 3, Max LIS till index 3 will be LIS[3] = 2 because only a[0] is less than a[3]. Hence longest sub sequence ending with a[3] will have length only of 2.

For i =4, i.e.5 Max LIS is again 3 which includes {2,4,5} or {2,3,5}

For i =5, i.e 7, Max LIS is 4 which includes {2,4,5,7} or {2,3,5,7} or {2,4,6,7}

For i =6, i.e 9, Max LIS is 5 which includes {2,4,5,7,9} or {2,3,5,7,9} or {2,4,6,7,9}

There are many problems which can be solved by finding longest increasing subsequence. For example

1. Given two river banks (visualization : two parallel lines), one bank has numbers written (1….n) in sorted order. On the other bank the numbers (1…n) are arranged randomly. A bridge can be formed from the ith point from bank 1 to ith point in bank 2. Find the max number of non-intersecting bridges you can form?

Just find longest increasing subsequence in non ordered number and that will be the solution.

2. Given a set of n types of rectangular 3-D boxes, where the ith box has height h(i), width w(i) and depth d(i) (all real numbers). You want to create a stack of boxes which is as tall as possible, but you can only stack a box on top of another box if the dimensions of the 2-D base of the lower box are each strictly larger than those of the 2-D base of the higher box.

There are many problems which can be solved by finding longest increasing subsequence. For example

1. Given two river banks (visualization : two parallel lines), one bank has numbers written (1….n) in sorted order. On the other bank the numbers (1…n) are arranged randomly. A bridge can be formed from the ith point from bank 1 to ith point in bank 2. Find the max number of non-intersecting bridges you can form?

Just find longest increasing subsequence in non ordered number and that will be the solution.

2. Given a set of n types of rectangular 3-D boxes, where the ith box has height h(i), width w(i) and depth d(i) (all real numbers). You want to create a stack of boxes which is as tall as possible, but you can only stack a box on top of another box if the dimensions of the 2-D base of the lower box are each strictly larger than those of the 2-D base of the higher box.

## Code to find longest increasing subsequence

Algorithm to

__find longest increasing subsequence__works in O(N^2) in time complexity with O(N) space complexity.