Question

Scenario
Create an algorithm to solve the maximum subarray problem. Find the non-empty, contiguous subarray of the input array whose values have the largest sum. You can see an example array with the maximum subarray indicated in the following diagram:

Screen Shot 2019-01-07 at 10.58.06 AM.png
The O(n2) brute force algorithm that tests all combinations for the start and end indices of the subarray is trivial to implement. Try to solve this using the divide and conquer algorithm.

Aim
To design and implement an algorithm to solve the maximum subarray problem with a better runtime than the O(n2) brute force algorithm, using a divide and conquer approach.

Prerequisites
You need to implement the maxSubarray() method of the MaximumSubarray class in the source code, which returns the sum of values for the maximum subarray of the input array. Assume that the sum always fits in an int, and that the size of the input array is at most 100,000.

public class MaximumSubarray {
public Integer maxSubarray(int[] a) {
return null;
}
}
The divide and conquer approach suggests that we divide the subarray into two subarrays of as equal size as possible. After doing so, we know that a maximum subarray must lie in exactly one of following three places:

Entirely in the left subarray
Entirely in the right subarray
Crossing the midpoint
Steps for Completion
The maximum subarray of the arrays on the left and right is given recursively, since those subproblems are smaller instances of the original problem.
Find a maximum subarray that crosses the midpoint.

Answer 1

I have attached the code for finding the maximum subarray sum using Divide and Conquer technique. Tha complexity of the code is O(nlog(n)). In the program, I have commented out the working of the algorithm. If you have any doubt, feel free to ask me.

MaximumSubarray.java:

import java.util.*;

public class MaximumSubarray{

    /*This function finds the max sum of subarray that
    crosses the middle element*/
    private Integer maxCrossingSum(int arr[], int left, int middle, int right)
    {
        //now we calculate maximum continuous sum in left part
        int sum = 0;
        int max_left_sum = arr[middle];
        for (int i = middle; i >= left; i--)
        {
            sum = sum + arr[i];
            if (sum > max_left_sum)
                max_left_sum = sum;
        }

        //now we calculate maximum continuous sum in right part
        sum = 0;
        int max_right_sum = arr[middle+1];
        for (int i = middle + 1; i <= right; i++)
        {
            sum = sum + arr[i];
            if (sum > max_right_sum)
            max_right_sum = sum;
        }
        //Now we need to return the sum of both maximum of left and max of right
        return max_left_sum + max_right_sum;
    }
  
    //this is helper function which performs recursion
    private Integer maxSubarrayHelper(int[] arr , int left , int right){
        //check if left == right , then there is single element , return
        if(left == right){
            return arr[left];
        }
        //get index of middle element
        int middle = (left + right) / 2;
        /*now we have three situation
        1) The max subarray lies completely in left half subarray
        2) The max subarray lies completely in right half subarray
        3) The max subarray contains elements of both right and left half subarray and crosses mid
        //Therefore we calculate each and return the maximum of three
        */
        return Math.max(Math.max(maxSubarrayHelper(arr, left, middle),//left half subarray,
                        maxSubarrayHelper(arr, middle + 1, right)),//right half subarray
                        maxCrossingSum(arr, left, middle, right)/*maximum crossing sum*/);
      
    }

    public Integer maxSubsrray(int arr[])
    {
        //call helper function
        return maxSubarrayHelper(arr , 0 , arr.length - 1);
    }

    //driver methods to test the code
    public MaximumSubarray(){

    }
    public static void main(String[] args){
        int[] arr = {-1 , -3, 4 , 5, -2, 4, 5, 7,-10 };
        System.out.println("Max Subarray Sum: " + new MaximumSubarray().maxSubsrray(arr));
    }
}

Code Screenshots:

Sample output for array: {-1 , -3, 4 , 5, -2, 4, 5, 7,-10 }