fork download
copy 
  1. import java.util.Random;
  2. import static java.lang.Integer.parseInt;
  3. import static java.lang.Math.max;
  4. import java.lang.IllegalArgumentException;
  5.  
  6. /**
  7.  * The MaxSubsequenceSum class contains implementations of three algorithms
  8.  * for solving the maximum subsequence sum problem.
  9.  * @author  Mike Jacobson
  10.  * @version 1.0, September 2008
  11.  */
  12. public class MaxSubsequenceSum {
  13.     static final int MAX_ARRAY_SIZE=100000;
  14.     static final int MAX_ENTRY_SIZE=1000;
  15.  
  16.  
  17.     /**
  18.      * Generates an array containing n random elements between -maxEntry and
  19.      * maxEntry.
  20.      *
  21.      * @return array containing n random elements between -maxEntry and maxEntry
  22.      * @param  n desired size of A
  23.      * @param  maxEntry elements of A will be randomly chosen between -maxEntry and maxEntry
  24.      * @throws IllegalArgumentException if n < 0, n > MAX_ARRAY_SIZE or maxEntry > MAX_ENTRY_SIZE
  25.      */
  26.     public static int [] randomArray(int n, int maxEntry)
  27.     {
  28.         // Enforce preconditions
  29. 	if (n <= 0)
  30. 	    throw new IllegalArgumentException("Negative array size: " + n);
  31.  
  32. 	if (n > MAX_ARRAY_SIZE)
  33. 	    throw new IllegalArgumentException("Array size = " + n + " bigger than MAX_ARRAY_SIZE = " + MAX_ARRAY_SIZE);
  34.  
  35. 	if (maxEntry > MAX_ENTRY_SIZE)
  36. 	    throw new IllegalArgumentException("Max entry size = " + maxEntry + " bigger than " + MAX_ENTRY_SIZE);
  37.  
  38.  
  39. 	// create A
  40. 	int [] A = new int[n];
  41.  
  42.  
  43. 	// fill A with random integers
  44. 	Random R = new Random();
  45. 	for (int i=0; i<n; ++i)
  46. 	    {
  47. 		int val = R.nextInt(2*maxEntry+1) - maxEntry;
  48. 		assert -maxEntry <= val && val <= maxEntry : "val = " + val + ", maxEntry = " + maxEntry;
  49. 		A[i] = val;
  50. 	    }
  51.  
  52.  
  53. 	// test postconditions
  54. 	assert A.length == n : "A.length = " + A.length + ", n = " + n;
  55. 	for (int i=0; i<n; ++i)
  56. 	    assert -maxEntry <= A[i] && A[i] <= maxEntry : "A[i] = " + A[i] + ", maxEntry = " + maxEntry; 
  57.  
  58. 	return A;
  59.     }
  60.  
  61.  
  62.  
  63.     /**
  64.      * Exhaustive search maximum subsequence sum algorithm.
  65.      * Finds and returns maximum sum in A by testing all valid indices i and j.
  66.      *
  67.      * @return value of the maximum subsequence sum in A
  68.      * @param A integer array
  69.      * @throws IllegalArgumentException if A is null or A.length > MAX_ARRAY_SIZE
  70.      */
  71.     public static int maxSubSum1(int [] A)
  72.     {
  73.         // enforce preconditions
  74.         if (A == null)
  75.             throw new IllegalArgumentException("A is null");
  76.  
  77.         if (A.length > MAX_ARRAY_SIZE)
  78.             throw new IllegalArgumentException("Array size = " + A.length + " bigger than MAX_ARRAY_SIZE = " + MAX_ARRAY_SIZE);
  79.  
  80.  
  81.         // compute the max subsequence sum of A using brute-force
  82.         int maxSum=0;
  83. 	int n = A.length;
  84.  
  85. 	for (int j=0; j<n; ++j) {
  86. 	    for (int i=0; i<=j; ++i) {
  87. 		int S = 0;
  88. 		for (int k=i; k <= j; ++k) {
  89. 		    S += A[k];
  90. 		}
  91.  
  92. 		if (S > maxSum)
  93. 		    maxSum = S;
  94. 	    }
  95. 	}
  96.  
  97.         // Postcondition: maxSum is the max subsequence sum of A
  98.         assert maxSum >= 0: maxSum;
  99.  
  100.         return maxSum;
  101.     }
  102.  
  103.  
  104.  
  105.  
  106.     /**
  107.      * Recursive maximum subsequence sum algorithm.
  108.      * Finds maximum sum in subarray spanning A[left],...,A[right].
  109.      *
  110.      * @return value of the maximum subsequence sum in A[left],...,A[right]
  111.      * @param A non-null integer array of length <= MAX_ARRAY_SIZE with entries between -MAX_ENTRY_SIZE and MAX_ENTRY_SIZE
  112.      * @param left left index of current subarray
  113.      * @param right  right index of current subarray
  114.      */
  115.     private static int maxSumRec(int [] A, int left, int right)
  116.     {
  117. 	// test preconditions of private function
  118. 	assert A != null;
  119. 	assert left >= 0 : left;
  120. 	assert right <= A.length : A.length;
  121.  
  122.  
  123. 	// base cases
  124.         if (left > right)
  125. 	    return 0;
  126.  
  127. 	if (left == right)
  128. 	    if (A[left] > 0)
  129. 		return A[left];
  130. 	    else
  131. 		return 0;
  132.  
  133.  
  134. 	// compute maximum subsequence sum for left and right halves of the array
  135. 	int center = (left + right) / 2;
  136. 	int maxLeftSum = maxSumRec(A,left,center);
  137. 	int maxRightSum = maxSumRec(A,center+1,right);
  138.  
  139.  
  140.  
  141. 	// compute largest sum in the left half containing A[center]
  142. 	int maxLeftBorderSum = 0, leftBorderSum = 0;
  143. 	for (int i=center; i>=left; --i)
  144. 	    {
  145. 		leftBorderSum += A[i];
  146. 		if (leftBorderSum > maxLeftBorderSum)
  147. 		    maxLeftBorderSum = leftBorderSum;
  148. 	    }
  149. 	// maxLeftBorderSum is the max subsequence sum of A[left],...,A[center]
  150.         //   that includes A[center]
  151.  
  152.  
  153.  
  154. 	// compute largest sum in the right half containing A[center+1]
  155. 	int maxRightBorderSum = 0, rightBorderSum = 0;
  156. 	for (int i=center+1; i<right; ++i)
  157. 	    {
  158. 		rightBorderSum += A[i];
  159. 		if (rightBorderSum > maxRightBorderSum)
  160. 		    maxRightBorderSum = rightBorderSum;
  161. 	    }
  162. 	// maxRightBorderSum is the max subsequence sum of
  163.         //   A[center+1],...,A[right] that includes A[center+1]
  164.  
  165.  
  166.  
  167.         int maxSum =  max(  max(maxLeftSum,maxRightSum), maxLeftBorderSum+maxRightBorderSum);
  168.  
  169. 	// the maximimum subsequence sum for A[left],...,A[right] is
  170. 	// max(maxLeftSum, maxRightSum, maxLeftBorderSum+maxRightBorderSum)
  171. 	assert maxSum >= 0 : maxSum;
  172.  
  173.         return maxSum;
  174.     }
  175.  
  176.  
  177.  
  178.  
  179.     /**
  180.      * Recursive maximum subsequence sum driver program.
  181.      * Finds maximum subsequence sum in A recursively.
  182.      *
  183.      * @return value of the maximum subsequence sum in A
  184.      * @param A integer array
  185.      * @throws IllegalArgumentException if A is null or A.length > MAX_ARRAY_SIZE
  186.      */
  187.     public static int maxSubSum2(int [] A)
  188.     {
  189. 	// enforce preconditions
  190. 	if (A == null)
  191. 	    throw new IllegalArgumentException("A is null");
  192.  
  193. 	if (A.length > MAX_ARRAY_SIZE)
  194. 	    throw new IllegalArgumentException("Array size = " + A.length + " bigger than MAX_ARRAY_SIZE = " + MAX_ARRAY_SIZE);
  195.  
  196.  
  197. 	// compute the max subsequence sum of A using a recursive (divide-and-conquer) method
  198. 	int maxSum =  maxSumRec(A,0,A.length-1);
  199.  
  200. 	// Postcondition: maxSum is the max subsequence sum of A
  201. 	assert maxSum >= 0: maxSum;
  202.  
  203. 	return maxSum;
  204.     }
  205.  
  206.  
  207.  
  208.  
  209.     /**
  210.      * Optimal efficiency maximum subsequence sum algorithm.
  211.      * Finds maximal subsequence sum in A using the fastest known algorithm.
  212.      *
  213.      * @return value of the maximum subsequence sum in A
  214.      * @param A integer array
  215.      * @throws IllegalArgumentException if A is null or A.length > MAX_ARRAY_SIZE
  216.      */
  217.     public static int maxSubSum3(int [] A)
  218.     {
  219. 	// enforce preconditions
  220. 	if (A == null)
  221. 	    throw new IllegalArgumentException("A is null");
  222.  
  223. 	if (A.length > MAX_ARRAY_SIZE)
  224. 	    throw new IllegalArgumentException("Array size = " + A.length + " bigger than MAX_ARRAY_SIZE = " + MAX_ARRAY_SIZE);
  225.  
  226.  
  227. 	int maxSum = 0, thisSum = 0;
  228.  
  229. 	for (int j=0; j<A.length-1; ++j)
  230. 	    {
  231. 		thisSum += A[j];
  232.  
  233. 		if (thisSum > maxSum)
  234. 		    maxSum = thisSum;
  235. 		else if (thisSum < 0)
  236. 		    thisSum = 0;
  237. 	    }
  238.  
  239. 	// Postcondition:  maxSum is the max subsequence sum of A
  240. 	assert maxSum >= 0 : maxSum;
  241.  
  242. 	return maxSum;
  243.     }
  244.  
  245.  
  246.  
  247.  
  248.     /**
  249.      *  Prints a message describing proper usage with respect to required
  250.      *  command line parameters and exits.
  251.      */
  252.     public static void usage()
  253.     {  
  254. 	System.out.println("Usage: java MaxSubsequenceSum arraySize maxEntry numArrays");
  255. 	System.out.println("  arraySize - number of elements per array");
  256. 	System.out.println("  maxEntry - each entry is between -maxEntry and maxEntry");
  257. 	System.out.println("  numArrays - number of different arrays to test");
  258. 	System.exit(1);
  259.     }
  260.  
  261.  
  262.     /**
  263.      *  Tests the three maximum subsequence sum functions on a common series
  264.      *  of random arrays.
  265.      *  Requires three command line parameters of type <code>int</code>:
  266.      *  <ul>
  267.      *   <li> arraySize (length of arrays to test)
  268.      *   <li> maxEntry (each array entry will be between -maxEntry and maxEntry)
  269.      *   <li> numArrays (number of random arrays to test)
  270.      *  </ul>
  271.     */
  272.     public static void main(String[] args)
  273.     {
  274. 	if (args.length != 3)  usage();
  275.  
  276. 	// gather command line arguments
  277. 	int n = parseInt(args[0]);
  278. 	int maxEntry = parseInt(args[1]);
  279. 	int num_arrays = parseInt(args[2]);
  280.  
  281. 	System.out.println("Testing " + num_arrays + " arrays");
  282. 	System.out.println("Array entries between " + -maxEntry + " and " + maxEntry);
  283. 	System.out.println(n + " elements in each array");
  284.  
  285.  
  286. 	// create num_arrays random arrays and compute the maximum
  287.         // subsequence sum using three different methods for each
  288.  
  289. 	for (int i=0; i<num_arrays; ++i)
  290. 	    {
  291. 		// create an array of random integers between
  292.                 // -max_int and max_int
  293. 		int [] A = null;
  294. 		try 
  295. 		    {
  296. 			A = randomArray(n,maxEntry);
  297. 		    }
  298. 		catch (IllegalArgumentException e)
  299. 		    {
  300. 			System.out.println(e);
  301. 			usage();
  302. 		    }
  303.  
  304. 		// compute maximum subsequence sum using exhaustive
  305.                 // search algorithm
  306. 		int max1 = maxSubSum1(A);
  307.  
  308. 		// compute maximum subsequence sum using recursive algorithm
  309. 		int max2 = maxSubSum2(A);
  310. 		assert max2 == max1 : "max1 = " + max1 + ", max2 = " + max2 + " (should be equal)";
  311.  
  312. 		// compute maximum subsequence sum using optimal algorithm
  313. 		int max3 = maxSubSum3(A);
  314. 		assert max3 == max2 : "max2 = " + max2 + ", max3 = " + max3 + " (should be equal)";
  315.  
  316. 		System.out.println("i=" + i + ", max1 = " + max1 + ", max2 = " + max2 + ", max3 = " + max3);
  317. 	    }
  318.     }
  319. }
Runtime error #stdin #stdout 0.31s 213696KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/3wbiT
language:
JavaScript (rhino 1.7.9)
created:
14 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!