MergeSort { public int findMaximum(int[] benefits, int low, int high) { int len = benefits.length; if (len <= 0) throw new ArithmeticException("Need more than one number in array."); if (low < 0 || low > len - 1 || high < 0 || high > len - 1 || low > high) throw new ArithmeticException("0 <= low <= high < arr.length"); int maxLeft, maxMiddle, maxRight; if (low == high) return benefits[low]; else { int mid = (low + high) / 2; maxLeft = findMaximum(benefits, low, mid); maxMiddle = maxBenefit(benefits, low, mid, high); maxRight = findMaximum(benefits, mid + 1, high); if (maxLeft > maxMiddle && maxLeft > maxRight) return maxLeft; else if (maxMiddle > maxLeft && maxMiddle > maxRight) return maxMiddle; else return maxRight; } }  int[] transfer(int[] benefits); int maxBenefit(int[] benefits, int low, int mid, int high); int findMaximum(int[] benefits, int low, int high);  }
@Test public void testFindMaximum() { int[] transferred = {13, -3, -25, 20, -3, -16, -23, 18, 20, -7, 12, -5, -22, 15, -4, 7}; int len = transferred.length; int max = mergeSort.findMaximum(transferred, 0, len - 1); System.out.print(max); assertEquals(43, max); }
@Test public void pressureTest() { int[] transferred = new int[10000]; int len = 10000; for (int i = 0; i < len; i++) transferred[i] = i + 1; System.out.println("data: [1 ~ " + transferred[9999] + "]"); long begin = System.currentTimeMillis(); int max = mergeSort.findMaximum(transferred, 0, 9999); long end = System.currentTimeMillis(); System.out.print("Result: " + max + ", and finished in " + (end - begin) + " millisecond"); assertEquals(50005000, max); }
@Test public void simple() { { int[] unSort = {0}; mergeSort.findMaximum(unSort, 0, 0); } { int[] unSort = {0, 1}; mergeSort.findMaximum(unSort, 0, 1); } { int[] unSort = {0, 1, 2}; mergeSort.findMaximum(unSort, 0, 2); } }