(In C++ code for Finding Maximum-Subarray)

In this lab assignment, your job is to implement the O(n log n) time divide and-conquer algorithm for the Max Subarray Problem; for the pseudo-code, it is:

Recall that in the problem, we are given as input an array A[1 n] of n integers, and would like to find i and j (1 i j n) such that A[i ] + A[i + 1] + + A[j ] is maximized.

FIND-MAXIMUM-SUBARRAY (A, low, high) 1 if high low 2return (low, high, A[low]) 3 else mid-(low + high)/2] 4(left-low, left-high, left-sum) - // base case: only one element (right-low, right-high, right-sum) (cross-low, cross-high, cross-sum) if left-sum > right-sum and left-sum > cross-sunm elseif right-sum > left-sum and right-sum > cross-sum else return (cross-low, cross-high, cross-sum) FIND-MAXIMUM-SUBarrAY (A, low, mid) FIND-MAXIMUM-SuBarrAY (A, mid + 1, high) FIND-MAX-CROSSING-SuBaRRAY (A, low, mid, high) return (left-low, left-high, left-sum) return (right-low, right-high, right-sum) 10 Input structure The input starts with an integer number n, which indicates the array size Then, the integers, All], Al2],,Aln], follow, one per line. , A2. -.. . An, follow, one per line. Output structure O utput the sum of integers in the max subarray, 1.e , A[r] + Ali, + j + Examples of input and output: Input 6> -3 -2 -3 10 -5 Output 16 Note that in this example, the max subarray is A[2..-5] So, we output Afi"] +.. + Alj*] - 11-2_31 10- 16 The outnut is only one number and has no white space