public class MaximumSubArraySum {
//Maximum Subarray Sum using Divide and Conquer algorithm
public static int MaximumSum(int[] Arr, int firstindex, int lastindex) {
if (lastindex == firstindex) {//if the first index and the last index of array are same
return Arr[ firstindex ];//it means array contains only one element
//and this element equals maximum subarray sum.
}
// Finding middle element's index of the array
int middle = ( firstindex + lastindex ) / 2;
// Finding maximum subarray sum for the left subarray
int leftMax = -1000000000;
int sum = 0;
for (int i = middle; i >= firstindex; i--) {
sum += Arr[ i ];//addition for sum
if (sum > leftMax) {
leftMax = sum;
}
}
// Find maximum subarray sum for the right subarray
int rightMax = -1000000000;//should be minimum value
sum = 0;
for (int i = middle + 1; i <= lastindex; i++) {
sum += Arr[ i ];//addition for sum
if (sum > rightMax) {
rightMax = sum;
}
}
// Recursive part
int maxLeftRight = Math.max (MaximumSum (Arr, firstindex, middle),//left part of the array
MaximumSum (Arr, middle + 1, lastindex));//right part of the array
// return maximum of the three
return Math.max (maxLeftRight, leftMax + rightMax);
}
C:\Users\Ayse\Desktop\Java\Programs\Games\ MaximumSubArraySum
}