• API
• FAQ
• Tools
• Archive
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.

Top