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. Starting code. public int maxSubarrayCross(int[] a, int l, int m, int h) { int leftSum = Integer.MIN_VALUE; int sum = 0; for (int i = m; i >= l; i--) { sum += a[i]; if (sum > leftSum) leftSum = sum; } int rightSum = Integer.MIN_VALUE; sum = 0; for (int i = m + 1; i <= h; i++) { sum += a[i]; if (sum > rightSum) rightSum = sum; } return leftSum + rightSum; } public int maxSubarrayAux(int[] a, int l, int h) { if (l == h) return a[l]; else { int m = (l + h) / 2; int bl = maxSubarrayAux(a, l, m); int br = maxSubarrayAux(a, m + 1, h); int bc = maxSubarrayCross(a, l, m, h); int best = Math.max(Math.max(bl, br), bc); return best; } } public Integer maxSubarray(int[] a) { return maxSubarrayAux(a , 0 , a.length -1); } public static void main(String[] args) { int[] a = {13, -3, -25, 20, -3, -16, -23, 18, 20, -7, 12, -5, -22, 15, -4, 7}; MaximumSubarray maxSubarray = new MaximumSubarray(); System.out.println("Maximum subarray = " + maxSubarray.maxSubarray(a)); }