How can i use divide and conquer to find the subarray with the maximum sum ?

Question

I need to use recusion to find the SUBARRAY with the max sum, i dont need the sum just the subarray, help please JAVA

Answer 1

You have the two indices which points on begin and end of current subarray. The main idea is to cut it for two parts of half size. The result is max of sumOnFirstHalf, sumOnSecondHalf, mixedSumOfTwoParts.

The first two sums is just the same for small parts then you have a recursion. The last sum you can count in linear time - the max sum on left from the point of cutting on two parts + max sum on right.

The summary complexity is O(nlogn) and it use divide and conquer.

To get array (not sum) just remember these indices.