SHARE
TWEET

SubArrayMaximumSum - First functional appproach

a guest Jun 2nd, 2014 189 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. // See http://codereview.stackexchange.com/questions/52270/finding-the-sub-array-with-the-maximum-sum-my-approach
  2.  
  3. public class MyApproach {
  4.  
  5.     public static void main(String[] args) {
  6.         assertArrayScan(5, 11,new int[]{4, -5, -1, 0, -2, 20, -4, -3, -2, 8, -1, 10, -1, -1 });
  7.         assertArrayScan(3, 8, new int[]{-5, 1, -3, 7, -1, 2, 1, -4, 6});
  8.         assertArrayScan(3, 6, new int[]{-5, 1, -3, 7, -1, 2, 1, -6, 5});
  9.         assertArrayScan(1, 4, new int[]{-5, 6, -3, -2, 7, -5, 2, 1, -7, 6});
  10.         assertArrayScan(2, 2, new int[]{-5, -2, -1, -4, -7});
  11.         assertArrayScan(0, 8, new int[]{4, 1, 1, 4, -4, 10, -4, 10, 3, -3, -9, -8, 2, -6, -6, -5, -1, -7, 7, 8});
  12.     }
  13.  
  14.         private static void assertArrayScan(int startIndex, int endIndex, int[] array) {
  15.                 System.out.println("Original : " + Arrays.toString(array));
  16.                 int[] expected = Arrays.copyOfRange(array, startIndex, endIndex + 1);
  17.                 System.out.println("Expecting: " + Arrays.toString(expected));
  18.                 int[] actual = scanArray(array);
  19.                 System.out.println("Actual   : " + Arrays.toString(actual));
  20.                 System.out.println();
  21.                 assertArrayEquals(expected, actual);
  22.         }
  23.  
  24.         private static int[] scanArray(int[] array) {
  25.                 if (array == null || array.length == 0)
  26.                         throw new IllegalArgumentException("Array cannot be null and must contain at least one element");
  27.                
  28.                 int maxStartingIndex = 0;
  29.                 int maxEndingIndex = 0;
  30.                 int max = array[0];
  31.                 outer:
  32.                 for (int i = 0; i < array.length; i++) {
  33.                         int value = array[i];
  34.                         if (value > max) {
  35.                                 max = value;
  36.                                 maxStartingIndex = i;
  37.                                 maxEndingIndex = i;
  38.                         }
  39.                         if (value < 0)
  40.                                 continue;
  41.                         System.out.println();
  42.                         System.out.println(String.format("Starting looping on %d, max is %d for indexes %d -- %d", i, max, maxStartingIndex, maxEndingIndex));
  43.                        
  44.                         boolean swapped = false;
  45.                         int currentSum = value;
  46.                         for (int j = i + 1; j < array.length; j++) {
  47.                                 int jValue = array[j];
  48.  
  49.                                 boolean innerPositive = jValue >= 0;
  50.                                 System.out.println(String.format("CurrentSum %d, i %d, j %d, swapped %s, innerPos %s, max is %d for index %d -- %d", currentSum, i, j, swapped, innerPositive, max, maxStartingIndex, maxEndingIndex));
  51.                                 if (!swapped && innerPositive) {
  52.                                         currentSum += jValue;
  53.                                         if (currentSum >= max) {
  54.                                                 max = currentSum;
  55.                                                 maxStartingIndex = i;
  56.                                                 maxEndingIndex = j;
  57.                                         }
  58.                                 }
  59.                                 else if (swapped && !innerPositive) {
  60.                                         currentSum += jValue;
  61.                                 }
  62.                                 else if (!swapped && !innerPositive) {
  63.                                         swapped = true;
  64.                                         if (currentSum >= max) {
  65.                                                 max = currentSum;
  66.                                                 maxStartingIndex = i;
  67.                                                 maxEndingIndex = j - 1;
  68.                                         }
  69.                                         currentSum += jValue;
  70.                                 }
  71.                                 else { // swapped && innerPositive
  72.                                         if (currentSum >= 0) {
  73.                                                 maxStartingIndex = i;
  74.                                                 currentSum += jValue;
  75.                                                 swapped = false;
  76.                                                 if (currentSum >= max) {
  77.                                                         maxEndingIndex = j;
  78.                                                         max = currentSum;
  79.                                                         System.out.println("New record: " + max + " from " + maxStartingIndex + " to " + maxEndingIndex);
  80.                                                 }
  81.                                         }
  82.                                         else {
  83.                                                 currentSum = 0;
  84.                                                 i = j - 1;
  85.                                                 break;
  86.                                         }
  87.                                 }
  88.                                 if (j == array.length - 1) {
  89.                                         break outer;
  90.                                 }
  91.                                
  92.                                 /**
  93.                                  * // 6, -3, -2, 7
  94.                                  * swapped              innerPositive   action
  95.                                  * false                true                    add to sum and continue
  96.                                  * true                 false                   Add to current sum, continue
  97.                                  * false                false                   set swapped = true. Check current sum. Also continue.
  98.                                  * true                 true                    Check if current sum >= 0. If it is, possibly save indexes and continue. Otherwise, reset current sum to zero and start over on the new index.
  99.                                  */
  100.                         }
  101.                 }
  102.                
  103.                 return Arrays.copyOfRange(array, maxStartingIndex, maxEndingIndex + 1);
  104.         }
  105.  
  106. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top