Skip to content

Embed URL

HTTPS clone URL

Subversion checkout URL

You can clone with
or
.
Download ZIP
Java: Maximum Subarray
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++;
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Something went wrong with that request. Please try again.