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.An example array with the maximum subarray indicated:

The O(n²) 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(n²) 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.