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