package longestmonotonicsubsequence;

/**
 * Title: LongestMonotonicSubsequence
 * Description: O(n^2) dynamic programming alg to find longest subsequence
 * Copyright: Copyright (c) 2002
 * @author Burt Rosenberg
 * @version 17 June 2002
 */

public class LongestMonotonicSubsequence {

   public static
   void main ( String [] args ) {

        int [] x = { 3, 1, 5, 2, 3, 6, 5 } ;

        int [] a = dynamicProgramming( x ) ;
        printArray( "input array:", x ) ;
        printArray("longest subsequence:", longestSubsequence(x,a)) ;
   }

   static void printArray( String title, int [] a ) {
      System.out.println(title);
      for ( int i=0; i<a.length; i++ ) System.out.print(a[i]+" ");
      System.out.println() ;
   }

   static
   int [] dynamicProgramming( int [] x ) {

      // the algorithm

      int [] a = new int[x.length] ;
      // a[i] <- longest monotonic s/seq of x[0...i] ending w/ x[i]

      for ( int i=0; i<a.length; i++ )
      {
         int maxSoFar = 0 ;
         for ( int j=0; j<i; j++ ) {
            if ( x[j]<x[i] && a[j]>maxSoFar ) maxSoFar = a[j] ;
         }
      a[i] = maxSoFar + 1 ;
      }
      return a ;
   }

   static
   int lengthOfLongestSubsequence(int [] a ) {
      int maxSoFar = 0 ;
      for ( int i=0; i<a.length; i++ ) if (a[i]>maxSoFar) maxSoFar = a[i] ;
      return maxSoFar ;
  }

  static
  int [] longestSubsequence(int [] x, int [] a ) {

     // reconstruct chain which is longest subsequence, working backwards

     int lols = lengthOfLongestSubsequence(a) ;
     int [] ss = new int[lols] ;
     int lastIndex ;
     for ( lastIndex=0; lastIndex<a.length; lastIndex++ ) {
        if ( a[lastIndex]==lols ) break ;
     }
     int ssIndex = ss.length-1 ;
     ss[ssIndex--] = x[lastIndex] ;
     for ( int i=lastIndex; i>=0; i-- ) {
        if ( x[i]<x[lastIndex] && a[i]==(a[lastIndex]-1) ) {
           ss[ssIndex--] = x[i] ;
           lastIndex = i ;
        }
     }
     return ss ;
  }

}