| 21 | |
| 22 | //optimization1 : Prefix Sum array |
| 23 | public static void maxSubarraySum2(int arr[]) { |
| 24 | int maxSum = Integer.MIN_VALUE; |
| 25 | |
| 26 | int prefix[] = new int[arr.length]; |
| 27 | prefix[0] = arr[0]; |
| 28 | for(int i=1; i<arr.length; i++) { |
| 29 | prefix[i] = prefix[i-1] + arr[i]; |
| 30 | } |
| 31 | |
| 32 | for(int i=0; i<arr.length; i++) { |
| 33 | for(int j=i+1; j<arr.length; j++) { |
| 34 | int currSum = i==0 ? prefix[j] : prefix[j] - prefix[i-1]; |
| 35 | maxSum = Math.max(maxSum, currSum); |
| 36 | } |
| 37 | } |
| 38 | |
| 39 | System.out.println("max subarray sum is : " + maxSum); |
| 40 | } |
| 41 | |
| 42 | //Kadane's Algorithm |
| 43 | public static void maxSubarraySum3(int arr[]) { |