For algorithm and explanation, read here.

Code implementation


public class MaxSumTest
{
/**
* Main method
* @param s
*/
public static void main(String s[])
{
int[] arr=new int[10];
arr=new int[]{10, -19 , 8 , 4, -5, 2, -1, 3, 8,-9};

int arrlength=arr.length/2;
int[] arr1=createarr(0,arrlength,arr);
int[] arr2=createarr(arrlength, arr.length,arr);
int sum=maxsum(arr1,arr2);
System.out.println(sum);
}

/**
* To find out maximum sum subarray, following divide and conquer technique is used
* 1. Divide the array in 2 equal parts, now there are 3 possibilities.
* a. Max sum subarray crosses the mid of original array, i.e. a part of solution is in left array and other in right. Finding this is simple as we just need to move backword on left subarray to find the maximum sum, and then move fwd on right array to find max, and finally add the two
* b. The other possibility is that max subarray is completely on left array. This means left subarray becomes main array and we discard right array. We will repeat the steps from 1.
* c. The last possibility is that max subarray is completely on right array. This means right subarray becomes main array and we discard left array. We will repeat the steps from 1.
*/
public static int maxsum(int[] arr1, int[] arr2)
{
int sum1=0;
int maxsum1=0;
int sum2=0;
int maxsum2=0;
int maxsum=0;

//1.a. Find maximum sum crossing the the mid of original array.
for(int i=arr1.length-1;i>=0;i–)
{
sum1=sum1+arr1[i];
if(maxsum1y)
if(x>z)
return x;
else
return z;
else
if(y>z)
return y;
else
return z;
}

/**
* Create a subarray from start to end
* @param start
* @param end
* @param arr
* @return
*/
public static int[] createarr(int start, int end, int[] arr)
{
int[] myarr=new int[end-start];
for(int i=start,j=0;i
Finish.