fork(7) download
copy 
  1. import java.io.BufferedReader;
  2. import java.io.InputStreamReader;
  3.  
  4. /**
  5.  * Created by Shreyans on 4/16/2015
  6.  */
  7.  
  8. class LNG_INC_SUB//Longest Increasing Subsequence
  9. {
  10.     public static void main(String[] args) throws Exception
  11.     {
  12.         BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
  13.         System.out.println("Enter Numbers Separated by Spaces to find their LIS\n");
  14.         String[] s1=br.readLine().split(" ");
  15.         int n=s1.length;
  16.         int[] a=new int[n];//Array actual of Numbers
  17.         String []ls=new String[n];// Array of Strings to maintain LIS for every element
  18.         for(int i=0;i<n;i++)
  19.         {
  20.             a[i]=Integer.parseInt(s1[i]);
  21.         }
  22.         int[]dp=new int[n];//Storing length of max subseq.
  23.         int max=dp[0]=1;//Defaults
  24.         String seq=ls[0]=s1[0];//Defaults
  25.         for(int i=1;i<n;i++)
  26.         {
  27.             dp[i]=1;
  28.             String x="";
  29.             for(int j=i-1;j>=0;j--)
  30.             {
  31.                 //First check if number at index j is less than num at i.
  32.                 // Second the length of that DP should be greater than dp[i]
  33.                 // -1 since dp of previous could also be one. So we compare the dp[i] as empty initially
  34.                 if(a[j]<a[i]&&dp[j]>dp[i]-1)
  35.                 {
  36.                     dp[i]=dp[j]+1;//Assigning temp length of LIS. There may come along a bigger LIS of a future a[j]
  37.                     x=ls[j];//Assigning temp LIS of a[j]. Will append a[i] later on
  38.                 }
  39.             }
  40.             x+=(" "+a[i]);
  41.             ls[i]=x;
  42.             if(dp[i]>max)
  43.             {
  44.                 max=dp[i];
  45.                 seq=ls[i];
  46.             }
  47.         }
  48.         System.out.println("Length of LIS is: " + max + "\nThe Sequence is: " + seq);
  49.     }
  50. }
Success #stdin #stdout 0.1s 320256KB
comments (?)
stdin
copy 
10 22 9 33 21 50 41 60 80
stdout
copy 
Enter Numbers Separated by Spaces to find their LIS

Length of LIS is: 6
The Sequence is: 10 22 33 41 60 80
https://ideone.com/sBiOQx
language:
Java (HotSpot 12)
created:
9 years ago
visibility:
public

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!