fork(2) download
copy 
  1. import java.util.*;
  2. public class Main {
  3.     public static void main(String[] args) {
  4.         int arr[]={10,22,9,33,21,50,41,40,60,55};
  5.         int lis[]=new int[arr.length];
  6.         for(int i=0;i<arr.length;i++){
  7.             lis[i]=1;
  8.         }
  9.         for(int i=1;i<arr.length;i++){
  10.             for(int j=0;j<i;j++){
  11.                 if(arr[i]>arr[j]&&lis[i]<lis[j]+1){
  12.                     lis[i]=lis[j]+1;
  13.                 }
  14.             }
  15.         }
  16.         int max=0;
  17.         for(int i=0;i<arr.length;i++){
  18.             if(max<lis[i])
  19.                 max=lis[i];
  20.         }
  21.         //**************Recursive Print LIS****************
  22.         int rIndex=-1;
  23.         for(int i=arr.length-1;i>=0;i--){
  24.             if(lis[i]==max){
  25.                  rIndex=i;
  26.                  break;
  27.             }
  28.         }
  29.         int res[]=new int[max];
  30.         printLISRecursive(arr,rIndex,lis,res,max,max);
  31.     }
  32.         private static void printLISRecursive(int[] arr, int maxIndex, int[] lis, int[] res, int i, int max) {
  33.         if(maxIndex<0)return;
  34.         if(max==1&&lis[maxIndex]==1&&i==1){
  35.             res[i-1]=arr[maxIndex];
  36. //            System.out.println("Using Print Recursion:");
  37.             for(int j=0;j<res.length;j++){
  38.                 System.out.print(res[j]+" ");
  39.             }
  40.             System.out.println();
  41.             return;
  42.         }
  43.         if(lis[maxIndex]==max){
  44.             res[i-1]=arr[maxIndex];
  45.             printLISRecursive(arr, maxIndex-1, lis, res, i-1, max-1);
  46.         }
  47.         printLISRecursive(arr, maxIndex-1, lis, res, i, max);
  48.     }
  49.  
  50. }
Success #stdin #stdout 0.07s 380224KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
10 22 33 40 55 
10 22 33 41 55 
10 22 33 50 55 
10 22 33 40 60 
10 22 33 41 60 
10 22 33 50 60
https://ideone.com/H3zte5
Print LIS
language:
Java (HotSpot 12)
created:
10 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!