/* * To change this template, choose Tools | Templates * and open the template in the editor. */ package XXXX; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.Iterator; import java.util.StringTokenizer; /** * * @author poochedi */ public class LongestIncreasingSubsequence { public static void main(String[] args) throws IOException { InputStreamReader iReader = new InputStreamReader(System.in); BufferedReader bReader = new BufferedReader(iReader); ArrayList seqList = new ArrayList(); ArrayList lngIncSeq = new ArrayList(); System.out.println("Enter a sequence of numbers seperated by space Hit enter to terminate"); String seqString = bReader.readLine(); if(seqString != null) { StringTokenizer tokenizer = new StringTokenizer(seqString); while(tokenizer.hasMoreTokens()) { seqList.add(tokenizer.nextToken()); } System.out.println("seqList " + seqList.toString()); } else System.out.println("No sequence"); //Now that I have the list I can find the increasing subseq Iterator seqItr = seqList.iterator(); //add the 1st to the result list int first = Integer.parseInt((String)seqItr.next()); lngIncSeq.add(first); System.out.println("lngIncSeq - 1st elem " + lngIncSeq.toString()); while(seqItr.hasNext()) { //every element is looked O(n) int next = Integer.parseInt((String) seqItr.next()); //access is O(1) if(lngIncSeq.size() < 2) { System.out.println("next " + next + " first " + first ); if (next < first) { //the new number is lesser than the already existing in the list lngIncSeq.remove(0); lngIncSeq.add(next); first = next; //lngIncSeq.set(0, next); System.out.println("lngIncSeq if next < first " + lngIncSeq.toString() ); } else if(next > first) { //append the new number to the already existing list lngIncSeq.add(next); } } else { //now that the result list is more than 2 in length see how the next num is w.r.to prev two numbers in the list int prev = (int) (lngIncSeq.get(lngIncSeq.size()-2)); //O(1) int pres = (int) (lngIncSeq.get(lngIncSeq.size()-1)); //O(1) if(next > pres && next > prev) { //add next to end of the list lngIncSeq.add(next); //O(n) added to end of the list } else if( next > prev && next < pres) { int index = lngIncSeq.indexOf(pres); lngIncSeq.remove(index); //O(n) removal from end of list lngIncSeq.add(next); //O(n) addition to end of list } //if next is less than both pres and prev, ignore it => no change to the existing result list } } System.out.println("lngIncSeq " + lngIncSeq.toString()); } }