**Objective: **The longest Increasing Subsequence (LIS) problem is to find the length of the longest subsequence in a given array such that all elements of the subsequence are sorted in increasing order.

OR

Given a array A[1,2,……,n] , calculate B[1,2….m] with B[i]**Example:**

int[] A = { 1, 12, 7, 0, 23, 11, 52, 31, 61, 69, 70, 2 }; length of LIS is 7 and LIS is {1, 12, 23, 52, 61, 69, 70}.

**Approach:**

**Optimal Substructure:**

LIS(i) - Length of longest increasing subsequence which includes element A[i] as its last element.## LIS(i) = 1 + Max

_{j=1 to i-1}{LIS(j)} if A[i]>A[j] for 1

**Overlapping Subproblems:**

If we solve using recursion for calculating the solution for jth index we will be solving the subproblems again which we had solved earlier while solving the solution for (j-1)th index.

Example: A[] = {3, 4, 1, 5} i=1 , LIS(1) = 1 i=2 , LIS(2) = 1+ Max(LIS(1)) = 1 +1 =2 (4>3) i=3 , LIS(3) = 1 (1<3, 1<4) i=4 , LIS(4) = 1+ Max(LIS(1),LIS(2), LIS(3)) = 1 + Max(1,2,1) = 3

**Code:**

This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.

Learn more about bidirectional Unicode characters

public class LongestIncreasingSubsequence { | |

public void findSubsequence(int[] arrA) { | |

int[] LIS = new int[arrA.length]; | |

for (int i = 0; i < arrA.length; i++) { | |

int max = –1; | |

for (int j = 0; j < i; j++) { | |

// check if previous elements > current element | |

if (arrA[i] > arrA[j]) { | |

// update the max from the previous entries | |

if (max == –1 || max < LIS[j] + 1) { | |

max = 1 + LIS[j]; | |

} | |

} | |

} | |

if (max == –1) { | |

// means none of the previous element has smaller than arrA[i] | |

max = 1; | |

} | |

LIS[i] = max; | |

} | |

// find the max in the LIS[] | |

int result = –1; | |

int index = –1; | |

for (int i = 0; i < LIS.length; i++) { | |

if (result < LIS[i]) { | |

result = LIS[i]; | |

index = i; | |

} | |

} | |

// Print the result | |

// Start moving backwards from the end and | |

String path = arrA[index] + " "; | |

int res = result–1; | |

for (int i = index–1; i >= 0; i—) { | |

if(LIS[i]==res){ | |

path = arrA[i] + " " + path; | |

res—; | |

} | |

} | |

System.out.println("Longest Increasing subsequence: " + result); | |

System.out.println("Actual Elements: " + path); | |

} | |

public static void main(String[] args) { | |

int[] A = { 1, 12, 7, 0, 23, 11, 52, 31, 61, 69, 70, 2 }; | |

LongestIncreasingSubsequence i = new LongestIncreasingSubsequence(); | |

i.findSubsequence(A); | |

} | |

} |

Output: Longest Increasing subsequence: 7 Actual Elements: 1 7 11 31 61 69 70

**NOTE**: To print the Actual elements –

- find the index which contains the longest sequence, print that index from main array.
- Start moving backwards and pick all the indexes which are in sequence (descending).
- If longest sequence for more than one indexes, pick any one.

From our code LIS[] =