import java.util.ArrayList;

public class Mar27 
{
    /** VErsion 4
     *
    public static ArrayList<String> generateAll( String s )
    {
        ArrayList<String> result = null;
        
        // Base case
        if( s.equals( "" ) )
        {
            result = new ArrayList<String>( );
            result.add( "" );
            return result;
        }
        
        String substring = s.substring( 0, s.length( ) - 1 );
        char lastChar = s.charAt( s.length( ) - 1 );
        
        ArrayList<String> subproblemResult = generateAll( substring );
        
        result = new ArrayList<String>( );
        for( String str : subproblemResult )
        {
            result.add( str );
            result.add( str + lastChar );
        }
        
        return result;
    }
     **/
 
/*
    public static ArrayList<String> generateAll( String s )
    {
        ArrayList<String> result = new ArrayList<String>( );
        generateAll( s, result );
        return result;
    }
    
    private static void generateAll( String s, ArrayList<String> result )
    {
        if( s.equals( "" ) )
            result.add( "" );
        else
        {
            char lastChar = s.charAt( s.length( ) - 1 ); 
            String substring = s.substring( 0, s.length( ) - 1 );
            
            generateAll( substring, result );
            int N = result.size( );
        
            for( int i = 0; i < N; i++ )
                result.add( result.get( i ) + lastChar );
        }
    } 
 **/

 
    public static ArrayList<String> generateAll( String s )
    {
        ArrayList<String> result = new ArrayList<String>( );
        generateAll( s, s.length( ) - 1, result );
        return result;
    }
    
    private static void generateAll( String s, int high, ArrayList<String> result )
    {
        if( high < 0 )
            result.add( "" );
        else
        {
            char lastChar = s.charAt( high );
            
            generateAll( s, high - 1, result );
            int N = result.size( );
        
            for( int i = 0; i < N; i++ )
                result.add( result.get( i ) + lastChar );
        }
    }
    
    /**
     ** VErsion #1: Try no driver
     **/
    public static ArrayList<String> generatePermutations( String s )
    {
        ArrayList<String> result = new ArrayList<String>( );
        
        if( s.length( ) <= 1 )
        {
            result.add( s );
            return result;
        }
        
        for( int i = 0; i < s.length( ); i++ )
        {
            char firstChar = s.charAt( i );
            String substring = s.substring( 0, i ) + s.substring( i + 1 );
            
            ArrayList<String> subproblem = generatePermutations( substring );
            for( String str : subproblem )
                result.add( firstChar + str );
        }
           
        return result;
    }
    
    public static double bestRatio( double [ ] arr )
    {
        if( arr.length == 0 )
            return 0.0;
        
        return bestRatio( arr, 0, arr.length - 1 );
    }
    
    public static double bestRatio( double [ ] arr, int low, int high )
    {
        if( low == high )
            return 1.0;
        
        int mid = ( low + high ) / 2;
        
        double bestEarly = bestRatio( arr, low, mid );
        double bestLate  = bestRatio( arr, mid + 1, high );
        
        int minIndex = low;  // Will be cheapest buy in the first half
        for( int i = low + 1; i <= mid; i++ )
            if( arr[ i ] < arr[ minIndex ] )
                minIndex = i;
        
        int maxIndex = mid + 1;  // Will be best sell point in the second half
        for( int j = mid + 2; j <= high; j++ )
            if( arr[ j ] > arr[ maxIndex ] )
                maxIndex = j;
        
        double bestLongTerm = arr[ maxIndex ] / arr[ minIndex ];
        
        return Math.max( Math.max( bestEarly, bestLate ), bestLongTerm );
    }
    
    
    public static void main( String [ ] args )
    {
        System.out.println( generatePermutations( "ab" ) );
        
        double [ ] arr = { 8, 5, 6, 3, 5, 4, 5, 6, 3, 5, 4, 2, 3, 8 };
        
        System.out.println( "Best ratio is: " + bestRatio( arr ) );
    }
}