public
Created

Java: Maximum Subarray

  • Download Gist
maxSubarray.java
Java
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181
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++;
}
}
}

Please sign in to comment on this gist.

Something went wrong with that request. Please try again.