## Thursday, 25 August 2016

### Longest Increasing Subsequence

LIS problem is to find the length of longest subsequence of a given sequence such that all elements of the subsequence are sorted in increasing order.

package com.dp;
import java.util.Stack;

public class LIS {
private static int findLIS(int[] array) {
int len = array.length;
int[] lis = new int[len];

/** Every itself a LIS. */
for (int i = 0; i < len; i++) {
lis[i] = 1;
}

/** Logic to update the lis sequence*/
for (int i = 1; i < len; i++) {
for (int j = 0; j < i; j++) {
if(array[i]>array[j]) {
lis[i] = Math.max(lis[j]+1, lis[i]);
}
}
}

int max = Integer.MIN_VALUE;
for (int i = 0; i < len; i++) {
if(max<lis[i]) {
max = lis[i];
}
}
printSequence(array,lis, max);
return max;
}

/**
* Print LIS sequence.
* @param array
* @param lis
* @param max
*/
private static void printSequence(int[] array, int[] lis, int max) {
Stack<Integer> stack = new Stack<>();

/** Print the sequence. */
for(int i = array.length-1; i >= 0; i--) {
if(lis[i] == max ) {
stack.push(array[i]);
-- max;
}
}

while(!stack.isEmpty()) {
System.out.print(" "+ stack.pop());
}
System.out.println();
}

public static void main(String[] args) {
int [] array = {15, 27, 14, 38, 26, 55, 46, 65, 85};

int seq = findLIS(array);

System.out.println("Longest Sequence #"+ seq);
}
}
Output:
15 27 38 46 65 85
Longest Sequence #6