Fundamental Algorithms Question

Stock Profit

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 Ai 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, ) 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