PLEASE USE A DIVIDE AND CONQUER ALGORITHM APPROACH IN C++! THANK YOU!

Given the forecasted price of a stock over time, write a divide and conquer algorithm that determines the best time to purchase and sell the stock (in order to maximize profit). It is assumed that a profit can be made (based on the forecast). It is assumed that the forecasted price of the stock over time is represented by a vector S of integers (for simplicity, we are assuming the stock price is integer-valued). Thus, the goal is to find two indices x and y (where 0 maxProfit (const vector & s, int start, int end) The return value is a vector of size 3. The first element is the maximum profit S[y] - S[x], the second element is the purchase time x, and the third element is the sell time y. Given the forecasted price of a stock over time, write a divide and conquer algorithm that determines the best time to purchase and sell the stock (in order to maximize profit). It is assumed that a profit can be made (based on the forecast). It is assumed that the forecasted price of the stock over time is represented by a vector S of integers (for simplicity, we are assuming the stock price is integer-valued). Thus, the goal is to find two indices x and y (where 0 maxProfit (const vector & s, int start, int end) The return value is a vector of size 3. The first element is the maximum profit S[y] - S[x], the second element is the purchase time x, and the third element is the sell time y. Hint: This problem is similar to the maximum subsequence problem. Test Case #1: S = {25, 1, 2, 11, 4, 8, 6,10) Maximum profit is S[3] - S[1] = 11 1 = 10. The algorithm should return the following vector: {10, 1, 3} Test Case #2: S = {17, 4, 8, 6, 10, 1, 2, 14} Test Case #3: S = {1, 2, 4, 8, 6, 12,10} Test your program using the above three test cases. For each test case, you should print out all three elements in the vector (that is, the maximum profit, the purchase time, and the sell time). Include both the source code and program output in your submission. For the source code file(s), please upload the actual.cpp file(s). For the program output, please take a screenshot of the window containing the program output (the screenshot should be in standard formats such as png, jpeg, or pdf). Also, please write out a recurrence relation for the time complexity T(n) and then express in Big-Theta notation. The time complexity should be no worse than O(n.log(n))