/*
 * 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());
    }
}
Advertisements