import java.util.Arrays;

/**
 * A program to find the maximum in an unsorted array
 * using three different methods (all recursive).
 * 
 * @author Mark Young (A00000000)
 */
public class FindMax {

    private static final boolean trace = true;

    public static void main(String[] args) {
        // create two sample arrays
        int[] arr1 = new int[]{6, 100, 3, -2, 8, 18, 5};
        int[] arr2 = new int[]{42, 17, -5, 86, 99};

        // 1st algorithm; 1st sample
        System.out.println("\nWorking from the back end....");
        System.out.println();
        System.out.println("Max of " + Arrays.toString(arr1) + ": "
                + findMaxFromBack(arr1, arr1.length));
        System.out.println();

        // 1st algorithm; 2nd sample
        System.out.println();
        System.out.println("Max of " + Arrays.toString(arr2) + ": "
                + findMaxFromBack(arr2, arr2.length));
        System.out.println();

        // 2nd algorithm; 1st sample
        System.out.println("\nWorking from the both ends....");
        System.out.println();
        System.out.println("Max of " + Arrays.toString(arr1) + ": "
                + findMaxFromBothEnds(arr1, 0, arr1.length - 1));
        System.out.println();

        // 3rd algorithm; 2nd sample
        System.out.println("\nWorking by splitting....");
        System.out.println();
        System.out.println("Max of " + Arrays.toString(arr2) + ": "
                + findMaxBySplitting(arr2, 0, arr2.length - 1));
        System.out.println();
        System.out.println();
    }

    public static int findMaxFromBack(int[] arr, int len) {
        showArrayPart(arr, 0, len - 1);
        if (len == 1) {
            return arr[0];
        } else {
            int max = findMaxFromBack(arr, len - 1);
            if (max > arr[len - 1]) {
                return max;
            } else {
                return arr[len - 1];
            }
        }
    }

    public static int findMaxFromBothEnds(int[] arr, int lo, int hi) {
        showArrayPart(arr, lo, hi);
        if (lo == hi) {
            return arr[lo];
        } else if (arr[lo] > arr[hi]) {
            return findMaxFromBothEnds(arr, lo, hi - 1);
        } else {
            return findMaxFromBothEnds(arr, lo + 1, hi);
        }
    }

    public static int findMaxBySplitting(int[] arr, int lo, int hi) {
        showArrayPart(arr, lo, hi);
        if (lo == hi) {
            return arr[lo];
        } else {
            int mid = lo + (hi - lo) / 2;
            int maxLo = findMaxBySplitting(arr, lo, mid);
            int maxHi = findMaxBySplitting(arr, mid + 1, hi);
            if (maxLo > maxHi) {
                return maxLo;
            } else {
                return maxHi;
            }
        }
    }

    private static void showArrayPart(int[] arr, int begin, int end) {
        System.out.print("...searching [");
        for (int i = begin; i < end; ++i) {
            System.out.print(arr[i] + ", ");
        }
        System.out.println(arr[end] + "]");
    }

}