Module 13 · Greedy · Best Time to Buy and Sell Stock II

Buy and sell stock II

Walk the days once: while the price falls, wait; at a low, buy; while it rises, hold; at the next high, sell. Why take every rise instead of one long trade? Buying at i, selling at j, buying at k and selling at l earns (arr[j] − arr[i]) + (arr[l] − arr[k]) = (arr[l] − arr[i]) + (arr[j] − arr[k]), and the high arr[j] is above the low arr[k] after it, so it is always more.

Each bar is a day's price. A band is a trade, from its buy price up to its sell price, with its profit.