Consider the following problem.

Problem 3-1 (Stock Profit) 10 (+6) Points Sometimes, computing "extra information can lead to more efficient divide-and-conquer algo- rithms. As an example, we will improve on the solution to the problem of maximizing the profit from investing in a stock (page 68-74) Suppose you are given an array A of n integers such that entry Ali is the value of a particular stock at time interval i. The goal is to find the time interval (i,j) such that your profit is maximized by buying at time i and selling at time j. For example, if the stock prices were monotone increasing, then (1, n) would be the interval with the maximal profit (A[n] A). More formally, the current formulation of the problem has the following input/output specification: Input: Array A of length n Output: Indices i