Maximum Subarray Problem: Difference between revisions
Jump to navigation
Jump to search
| Line 11: | Line 11: | ||
The maximum subarray problem is useful to solve the following problem: | The maximum subarray problem is useful to solve the following problem: | ||
Assuming we have access to stock prices of a company | Assuming we have access to stock prices of a company for a number of days, and the price does not change during a day, determine what would have been the best day to buy and the best day to sell one unit of stock to make the maximum profit. | ||
If we maintain the stock prices in an array, for 4 days (0-3) as follows price[0] = 10, price[1]=8, price[2]=12 and price[3]=11, then we would have made the most profit buying on day 1 at 8 and selling on day 2 at 12 (profit of 4). | If we maintain the stock prices in an array, for 4 days (0-3) as follows price[0] = 10, price[1]=8, price[2]=12 and price[3]=11, then we would have made the most profit buying on day 1 at 8 and selling on day 2 at 12 (profit of 4). | ||
Revision as of 22:03, 9 August 2018
External
- CLRS page 68
Internal
Overview
The maximum subarray problem is useful to solve the following problem:
Assuming we have access to stock prices of a company for a number of days, and the price does not change during a day, determine what would have been the best day to buy and the best day to sell one unit of stock to make the maximum profit.
If we maintain the stock prices in an array, for 4 days (0-3) as follows price[0] = 10, price[1]=8, price[2]=12 and price[3]=11, then we would have made the most profit buying on day 1 at 8 and selling on day 2 at 12 (profit of 4).