Description

I: https://oj.leetcode.com/problems/best-time-to-buy-and-sell-stock/

The first problem requires that we compute the possible maximum profit for at most one transaction.

II: https://oj.leetcode.com/problems/best-time-to-buy-and-sell-stock-ii/

The first problem requires that we compute the possible maximum profit for at any number of transactions.

III: https://oj.leetcode.com/problems/best-time-to-buy-and-sell-stock-iii/

The first problem requires that we compute the possible maximum profit for two transactions.

Analysis

Problem I

It is easy to solve the first problem by iterating the price vector just once. We keep the currently smallest stock price during the iteration and we update the maximum profit iteratively by

where $maxProfitLeft[t]$ is the possible maximum profit during $[0,t]$ and $maxProfitLeft[0] = 0$.

Problem II

It is even easier to solve the second problem. As long as price[t] > price[t-1], we make a transaction. This strategdy will lead to maximum profit.

Problem III

For the third question, the trivial thought would be that we enumerate the seperate time point of the two transactions and use the solution in problem I as subprocess to find the best separate point and thus the maximum profit. In this case, the time complexity is $O(n^2)$. Then we notice that there exists redundant computation in this procedure. There is a better way to avoid the redundant computation.

We compute $maxProfitLeft[t]$ as we did in problem I.

Then we define $maxProfitRight[t]$ indicating the maximum profit we can get from one transaction during the time $[t, T]$, where $T$ is the total number of time points, or the size of array $prices[]$. The way to compute it is

where $maxProfitLeft[T+1] = 0$.

Then the maximum profit for two non-overlapping transactions is

Thus the time complexity of this solution is $O(n)$.

Solution

The implementations are slightly different from the algorithm descriptions out of efficiency and convenience reasons.

Problem I

 1 class Solution {
 2 public:
 3     int maxProfit(vector<int> &prices) {
 4       int minPrice = INT_MAX;
 5       int maxProfit = 0;
 6       for (int i = 0; i < prices.size(); ++ i){
 7         minPrice = min(minPrice, prices[i]);
 8         maxProfit = max(prices[i] - minPrice, maxProfit);
 9       }
10       return maxProfit;
11     }
12 };

Problem II

 1 class Solution {
 2 public:
 3     int maxProfit(vector<int> &prices) {
 4     	int profit = 0;    	    	
 5     	//size_t is unsigned and thus tranformed into int, in case of prices.size()=0
 6   		for (int i = 0; i < (int)prices.size()-1; ++ i)    		
 7 			profit += (prices[i+1] > prices[i])? (prices[i+1] - prices[i]):0;
 8   		return profit;   
 9     }
10 };

Problem III

 1 class Solution {
 2 public:
 3     int maxProfit(vector<int> &prices) {
 4         int nPrice = prices.size();
 5         int curMin = INT_MAX;
 6         int maxProfitFromLeft[nPrice+1];
 7         maxProfitFromLeft[0] = 0;
 8         for (int i = 0; i < nPrice; ++ i){
 9             curMin = min(prices[i], curMin);
10             maxProfitFromLeft[i] = max(prices[i] - curMin, maxProfitFromLeft[i]);
11             maxProfitFromLeft[i+1] = maxProfitFromLeft[i];
12         }
13         int totalMaxProfit = 0;
14         int curMax = INT_MIN;
15         for (int i = nPrice-1; i >= 0; i --){
16             curMax = max(prices[i], curMax);
17             totalMaxProfit = max(maxProfitFromLeft[i] + curMax - prices[i], totalMaxProfit);                
18         }
19         return totalMaxProfit;
20     }
21 };