public class FindMax
1: import java.util.Arrays;
3: /**
4: * A program to find the maximum in an unsorted array
5: * using three different methods (all recursive).
6: *
7: * @author Mark Young (A00000000)
8: */
9: public class FindMax {
11: private static final boolean trace = true;
13: public static void main(String[] args) {
14: // create two sample arrays
15: int[] arr1 = new int[]{6, 100, 3, -2, 8, 18, 5};
16: int[] arr2 = new int[]{42, 17, -5, 86, 99};
18: // 1st algorithm; 1st sample
19: System.out.println("\nWorking from the back end....");
20: System.out.println();
21: System.out.println("Max of " + Arrays.toString(arr1) + ": "
22: + findMaxFromBack(arr1, arr1.length));
23: System.out.println();
25: // 1st algorithm; 2nd sample
26: System.out.println();
27: System.out.println("Max of " + Arrays.toString(arr2) + ": "
28: + findMaxFromBack(arr2, arr2.length));
29: System.out.println();
31: // 2nd algorithm; 1st sample
32: System.out.println("\nWorking from the both ends....");
33: System.out.println();
34: System.out.println("Max of " + Arrays.toString(arr1) + ": "
35: + findMaxFromBothEnds(arr1, 0, arr1.length - 1));
36: System.out.println();
38: // 3rd algorithm; 2nd sample
39: System.out.println("\nWorking by splitting....");
40: System.out.println();
41: System.out.println("Max of " + Arrays.toString(arr2) + ": "
42: + findMaxBySplitting(arr2, 0, arr2.length - 1));
43: System.out.println();
44: System.out.println();
45: }
47: public static int findMaxFromBack(int[] arr, int len) {
48: showArrayPart(arr, 0, len - 1);
49: if (len == 1) {
50: return arr[0];
51: } else {
52: int max = findMaxFromBack(arr, len - 1);
53: if (max > arr[len - 1]) {
54: return max;
55: } else {
56: return arr[len - 1];
57: }
58: }
59: }
61: public static int findMaxFromBothEnds(int[] arr, int lo, int hi) {
62: showArrayPart(arr, lo, hi);
63: if (lo == hi) {
64: return arr[lo];
65: } else if (arr[lo] > arr[hi]) {
66: return findMaxFromBothEnds(arr, lo, hi - 1);
67: } else {
68: return findMaxFromBothEnds(arr, lo + 1, hi);
69: }
70: }
72: public static int findMaxBySplitting(int[] arr, int lo, int hi) {
73: showArrayPart(arr, lo, hi);
74: if (lo == hi) {
75: return arr[lo];
76: } else {
77: int mid = lo + (hi - lo) / 2;
78: int maxLo = findMaxBySplitting(arr, lo, mid);
79: int maxHi = findMaxBySplitting(arr, mid + 1, hi);
80: if (maxLo > maxHi) {
81: return maxLo;
82: } else {
83: return maxHi;
84: }
85: }
86: }
88: private static void showArrayPart(int[] arr, int begin, int end) {
89: System.out.print("...searching [");
90: for (int i = begin; i < end; ++i) {
91: System.out.print(arr[i] + ", ");
92: }
93: System.out.println(arr[end] + "]");
94: }
96: }