Max Subarray (PLEASE WRITE CODE IN C++)

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, see page 72 in the textbook. 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.

HERE IS THE PSEUDOCODE

Please write this in C++ using this pseudocde

Max 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, see page 72 in the textbook. Recall that in the problem, we are given as input an array A n of n integers, and would like to find i and j' (1sisj such that AiAi1+Aj is maximized Input structure The input starts with an integer number n, which indicates the array size. Then, the integers, AllI, Al2,Alnl, follow, one per line Output the sum of integers in the max subarray, ie., Ali"] + Ali, + Output structure .+Ai] +