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

No comments:

Post a Comment

Related Posts Plugin for WordPress, Blogger...