| 3 | |
| 4 | |
| 5 | public static int MaximumSum(int[] Arr, int firstindex, int lastindex) { |
| 6 | |
| 7 | if (lastindex == firstindex) {//if the first index and the last index of array are same |
| 8 | return Arr[ firstindex ];//it means array contains only one element |
| 9 | //and this element equals maximum subarray sum. |
| 10 | } |
| 11 | |
| 12 | // Finding middle element's index of the array |
| 13 | int middle = ( firstindex + lastindex ) / 2; |
| 14 | |
| 15 | // Finding maximum subarray sum for the left subarray |
| 16 | |
| 17 | int leftMax = -1000000000; |
| 18 | int sum = 0; |
| 19 | for (int i = middle; i >= firstindex; i--) { |
| 20 | sum += Arr[ i ];//addition for sum |
| 21 | if (sum > leftMax) { |
| 22 | leftMax = sum; |
| 23 | } |
| 24 | } |
| 25 | |
| 26 | // Find maximum subarray sum for the right subarray |
| 27 | int rightMax = -1000000000;//should be minimum value |
| 28 | sum = 0; |
| 29 | for (int i = middle + 1; i <= lastindex; i++) { |
| 30 | sum += Arr[ i ];//addition for sum |
| 31 | if (sum > rightMax) { |
| 32 | rightMax = sum; |
| 33 | } |
| 34 | } |
| 35 | |
| 36 | // Recursive part |
| 37 | int maxLeftRight = Math.max (MaximumSum (Arr, firstindex, middle),//left part of the array |
| 38 | MaximumSum (Arr, middle + 1, lastindex));//right part of the array |
| 39 | |
| 40 | // return maximum of the three |
| 41 | return Math.max (maxLeftRight, leftMax + rightMax); |
| 42 | } |
| 43 | |
| 44 | C:\Users\Ayse\Desktop\Java\Programs\Games\ MaximumSubArraySum |
| 45 | } |