Best Time To Buy And Sell Stock - Any number of times - Overlapping Transactions

Problem

Your algorithms have become so good at predicting the market that you now know what the share price of Wooden Orange Toothpicks Inc. (WOT) will be for the next number of days.

Each day, you can either buy one share of WOT, sell any number of shares of WOT that you own, or not make any transaction at all. What is the maximum profit you can obtain with an optimum trading strategy?

Complete the stockmax function in the editor below.

stockmax has the following parameter(s):

• prices: an array of integers that represent predicted daily stock prices

Examples

Example 1:

Input: prices=[1,2]
Output: 1
Explanation: Buy one share day one, and sell it day two for a profit of 1. Return 1.

Example 2:

Input: prices=[2,1]
Output: 1
Explanation: No profit can be made so you do not buy or sell stock those days. Return 0.

Solution

Method 1 - Track Max on Right to Sell the Stock

Consider the following prices:

1 3 1 2

Our objective is to create another array that holds the maximum future price, including the current day (we can buy and sell on the same day if future prices are lower).

Day 1 -> Maximum future price = 3
Day 2 -> Maximum future price = 3
Day 3 -> Maximum future price = 2
Day 4 -> Maximum future price = 2

We achieve this by iterating backwards through the prices:

Day 4 -> m = 2
Day 3 -> 1 < 2 -> m = 2
Day 2 -> 3 > 2 -> m = 3
Day 1 -> 1 < 3 -> m = 3

Code

Java

public static long getMaxProfit(int[] prices) {
	long profit = 0L;
	int maxSoFar = 0;
	for (int i = prices.length - 1; i >= 0 ; i--) {
		if (prices[i] >= maxSoFar) {
			maxSoFar = prices[i];
		}
		profit += maxSoFar - prices[i];
	}
	return profit;
}