Maximum Subarray Sum using Divide and Conquer

You are given an array of n integers. Your task is to compute the maximum subarray sum by applying the Divide and Conquer technique. More formally, given an array \(A = [a_1, a_2, \dots, a_n]\), find the largest possible sum of a contiguous subarray.

The maximum subarray sum can be defined recursively as:

[ \text{maxSubArraySum}(A) = \max\begin{cases} \text{maxSubArraySum}(A_{left}) \ \text{maxSubArraySum}(A_{right}) \ \text{maxCrossingSum}(A) \end{cases} ]

where the maxCrossingSum is the sum of elements from the left and right sides that crosses the midpoint. Implement this algorithm and output the maximum subarray sum.

inputFormat

The input is given via standard input (stdin) and consists of two lines.

The first line contains an integer n representing the number of elements in the array.

The second line contains n space-separated integers denoting the elements of the array.

outputFormat

Print the maximum subarray sum to standard output (stdout) on a single line.## sample

5
2 3 4 5 7

21