1. Implement the pseudo algorithm of the Find Maximum Subarray problem using a divide and conquer approach to find a contiguous subarray whose values have the largest sum. Given the input and output requirements, your implement should follow the pseudocode provided in the textbook and lecture. You can simulate a period of 100 days with a randomly generated price ranging from $50 to $120 and calculate daily changes in prices from the generated prices. Use a table below as a model for 17 days, prices, and changes in price.

Day	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16
Price	100	113	110	85	105	102	86	63	81	101	94	106	101	97	94	90	97
change		13	-3	-25	20	-3	-16	-23	18	20	-7	12	-5	-22	15	-4	7

Inputs: stock prices for 100 days

Outputs: a sequence of 100 days

prices and price changes for 100 days

i and j indices indicating low and high index for the largest sum on each subarray of left, right and cross

a max profit identifying i and k indices calculated from the subarray

2. Upload your project folder (zip or source file) along with a screenshot of the program execution through Assignment 2 of Submit Assignments option in Blackboard. Include a header at the beginning of the code with your name, date submitted, and a brief description of the assignment, and makes sure to add relevant comments throughout the code

FIND-MAXIMUM-SUBARRAY (A, low, high)

1 if high == low

2 return (low. high. Allow]) // base case: only one element

3 else mid= L(low + high)/2]

4 (left-low, left-high, left-sum) =

FIND-MAXIMUM-SUBARRAY (A, low, mid)

5 (right-low, right-high, right-sum)=

FIND-MAXIMUM-SUBARRAY (A, mid + 1. high)

6 (cross-low, cross-high, cross-sum) =

FIND-MAX-CROSSING-SUBARRAY(A, low.mid, high)

7 if left-sum >= right-sum and left-sum >= cross-sum

8 return (left-low, left-high, left-sum)

9 elseif right-sum >= left-sum and right-sum >=cross-sum

10 return (right-low.right-high, right-sum)

11 else return (cross-low, cross-high.cross-sum)

FIND-MAX-CROSSING-SUBARRAY(A, low.mid.high)

1 left-sum =-infinity sign

2 sum=0

3 for i = mid downto low

4 sum = sum+A[i]

5 if sum > left-sum

6 left-sum = sum

7 max-left =i

8 right-sum = - infinity sign

9sum=0

10 for j = mid+1 to high

11 sum = sum + A[jI

12 if sum >right-sum

13 right-sum = sum

14 max-right = j

15 return (max-left.max-right, left-sum + right-sum)