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

}