Java: Maximum Subarray

maxSubarray.java

import java.util.*;

public class maxSubarray {
	static boolean switchToBrute = false;
	static boolean warmup = true;

	public static int maxSubarray(int[] A, int lo, int hi) {
		int sum, max;
		max = A[1];
		for (int i = lo; i <= hi; i++) {
			sum = 0;
			for (int j = i; j <= hi; j++) {
				sum += A[j];
				if (sum > max) {
					max = sum;
				}
			}
		}

		return max;
	}

	public static int find_max_subarray_with_brute(int[] A, int low, int hi) {
		int switchvalue = (warmup) ? 100 : 1000;
		if (low == hi) {
			return A[low];
		} else {
			int mid = (int) Math.floor((low + hi) / 2);
			int n = mid - low;
			int leftSum = (n > switchvalue) ? find_max_subarray(A, low, mid) : maxSubarray(A, low, mid);
			int rightSum = (n > switchvalue) ? find_max_subarray(A, mid + 1, hi) : maxSubarray(A, mid + 1, hi);
			int crossSum = find_max_crossing_subarray(A, low, mid, hi);
			if (leftSum >= rightSum && leftSum >= crossSum) {
				return leftSum;
			} else if (rightSum >= leftSum && rightSum >= crossSum) {
				return rightSum;
			} else {
				return crossSum;
			}
		}
	}

	public static int find_max_subarray(int[] A, int low, int hi) {
		if (low == hi) {
			return A[low];
		} else {
			int mid = (int) Math.floor((low + hi) / 2);
			int leftSum = find_max_subarray(A, low, mid);
			int rightSum = find_max_subarray(A, mid + 1, hi);
			int crossSum = find_max_crossing_subarray(A, low, mid, hi);
			if (leftSum >= rightSum && leftSum >= crossSum) {
				return leftSum;
			} else if (rightSum >= leftSum && rightSum >= crossSum) {
				return rightSum;
			} else {
				return crossSum;
			}
		}
	}

	public static int find_max_crossing_subarray(int[] A, int low, int mid,
			int hi) {
		int leftSum = Integer.MIN_VALUE;
		int rightSum = Integer.MIN_VALUE;
		int sum = 0;
		for (int i = mid; i >= low; i--) {
			sum += A[i];
			if (sum > leftSum) {
				leftSum = sum;
			}
		}

		sum = 0;
		
		for (int j = mid + 1; j <= hi; j++) {
			sum += A[j];
			if (sum > rightSum) {
				rightSum = sum;
			}
		}
		return leftSum + rightSum;
	}

	public static int[] construct_random_array(int length) {
		int[] A = new int[length];
		Random r = new Random(System.nanoTime());
		for (int i = 0; i < length; i++)
			A[i] = r.nextInt() % 10;

		return A;
	}

	public static void print_array(int[] A) {
		System.out.print("<");
		for (int i = 0; i < A.length - 1; i++)
			System.out.print(A[i] + ",");
		System.out.println(A[A.length - 1] + ">");
	}

	public static void main(String[] args) {
		long start, stop, elapsedBrute, elapsedRecursive, ratio;
		int A[];
		int size = 75;
		int j = 1;
		int maxB, maxR;
		maxB = maxR = 0;
		start = stop = 0;

		if (args.length > 0) {
			switchToBrute = Boolean.parseBoolean(args[0]);
		}
		if (args.length > 1) {
			warmup = Boolean.parseBoolean(args[1]);
		}
		
		System.out.format("Running %s switching to bruteforce and %s warmup%n", switchToBrute ? "with" : "without", warmup ? "with" : "without");
			
		System.out.format("%-4s%-8s%-10s%-10s%12s%15s%10s%n", "#", "n", "maxBrute",
				"maxRecur", "brute time", "recursive time", "ratio");
		
		String pattern = "%-4d%-8d%-10d%-10s%12d%15d%10.3f%n";
		
		if (warmup) {
			for (int i = 1; i < 15; i++) {
				A = construct_random_array(5000);

				// Test of Bruteforce
				start = System.nanoTime();
				maxB = maxSubarray(A, 0, A.length - 1);
				stop = System.nanoTime();
				elapsedBrute = (stop - start) / 1000;

				// Test of recursive
				start = System.nanoTime();
				
				if (switchToBrute) {
					maxR = find_max_subarray_with_brute(A, 0, A.length - 1);
				} else {
					maxR = find_max_subarray(A, 0, A.length - 1);
				}
				stop = System.nanoTime();
				
				elapsedRecursive = (stop - start) / 1000;

				System.out.format(pattern, i, A.length, maxB, maxR, elapsedBrute,
						elapsedRecursive, (elapsedBrute * 1.000)
								/ (elapsedRecursive * 1.000));
			}
			System.out.println("---------");

		}

		for (int i = 1; i < 30; i++) {
			A = construct_random_array(j * size);

			// Test of Bruteforce
			start = System.nanoTime();
			maxB = maxSubarray(A, 0, A.length - 1);
			stop = System.nanoTime();
			elapsedBrute = (stop - start) / 1000;

			// Test of recursive
			start = System.nanoTime();
			
			if (switchToBrute) {
				maxR = find_max_subarray_with_brute(A, 0, A.length - 1);
			} else {
				maxR = find_max_subarray(A, 0, A.length - 1);
			}
			
			stop = System.nanoTime();
			elapsedRecursive = (stop - start) / 1000;

			System.out.format(pattern, i, A.length, maxB, maxR, elapsedBrute,
					elapsedRecursive, (elapsedBrute * 1.000)
							/ (elapsedRecursive * 1.000));

			j++;
		}
	}
}