[LeetCode] Best Time to Buy and Sell Stock I && II && III

Best Time to Buy and Sell Stock I

Problem Statement (link):

Say you have an array for which the ith element is the price of a given stock on day i.
If you were only permitted to complete at most one transaction (ie, buy one and sell one share of the stock), design an algorithm to find the maximum profit.

Analysis:
The max profit at day i is the difference between prices[i] and the min price before day i. Thus, the max profit until day i is the max among all days before and including day i. We traverse the prices vector and store the min value we found so far, and calculate the max profit of day i in use of the min, update the overall  max profit if new max is larger.

This algorithm has O(n) in time complexity and with constant space complexity.

Code:

class Solution {
public:
    int maxProfit(vector<int> &prices) {
        if (prices.empty() || prices.size()==1) return 0;
        int profit = 0;
        int minPrice = prices[0];
        int len = prices.size();
        for (int i=0; i<len; i++) {
            if (prices[i]<minPrice)
                minPrice = prices[i];
            else
                profit = max(profit, prices[i]-minPrice);
        }
        return profit;
    }
};

Best Time to Buy and Sell Stock II

Problem Statement (link):

Say you have an array for which the ith element is the price of a given stock on day i.
Design an algorithm to find the maximum profit. You may complete as many transactions as you like (ie, buy one and sell one share of the stock multiple times). However, you may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

Analysis:
The problem is not well-stated, judging from the answer, it implies that you are allowed to sell and buy stock at the same day.

With that, the solution is simple. We make a profit by buying at day i and sell at day j as long as i<j and prices[i]<prices[j]. Thus, we simply traverse the vector and accumulate all the differences between day pairs.

This algorithm has O(n) in time complexity and with constant space complexity.

Code:

class Solution {
public:
    int maxProfit(vector<int> &prices) {
        if (prices.empty() || prices.size()==1) return 0;
        int profit = 0;
        for (int i=0; i<prices.size()-1; i++) {
            if (prices[i+1]>prices[i])
                profit += prices[i+1]-prices[i];
        }
        return profit;
    }
};

Best Time to Buy and Sell Stock III

Problem Statement (link):

Say you have an array for which the ith element is the price of a given stock on day i.
Design an algorithm to find the maximum profit. You may complete at most two transactions.
Note:
You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

Analysis:
As we may complete two transaction, the first thought is to separate the vector into two parts and find max profit for each parts. Sol 1 is the implementation of this algorithm. However, it yields TLE in a large test case.

If we think about the previous algorithm, we notice that we scanned many entries multiple times, which piles up to the time complexities. Sol 2 is an O(n) algorithm. In this algorithm, we first scan from left to right to get a vector of max profit that ends at each day i in O(n) time; then we scan from right to left to get another vector of max profit that starts at each day i in O(n) time; finally, we calculate the max profit overall by finding out the day that separate two transactions.

Code:
Sol 1: O(n^2) - TLE

class Solution {
public:
    int maxProfit(vector<int> &prices) {
        if(prices.empty() || prices.size()==1) return 0;
        int profit1 = 0;    // max profit from 0:i
        int profit2 = 0;    // max profit from i:n
        int min1 = 0;
        int min2 = 0;
        int n = prices.size();
        int profit = 0;
        for (int i=0; i<n; i++) {
            // From 0-i
            min1 = prices[0];
            for (int p=0; p<=i; p++){
                if (prices[p]<min1) min1=prices[p];
                else profit1 = max(profit1, prices[p]-min1);
            }
            min2 = prices[i];
            for (int p=i; p<n; p++){
                if (prices[p]<min2) min2=prices[p];
                else profit2 = max(profit2, prices[p]-min2);
            }
            
            profit = max(profit, profit1+profit2);
        }
        return profit;
    }
};

Sol 2: O(n)

class Solution {
public:
    int maxProfit(vector<int> &prices) {
        if (prices.empty() || prices.size()==1) return 0;
        int minp=prices[0]; int profit=0; int maxProfit=0;
        vector<int> left; vector<int> right;

        // traverse from left to right
        for (int i=0; i<prices.size(); i++) {
            if (prices[i]<minp) minp=prices[i];
            else profit=max(profit, prices[i]-minp);
            left.push_back(profit);
        }

        // traverse from right to left
        int maxp=prices[prices.size()-1]; profit=0;
        for (int i=prices.size()-1; i>=0; i--) {
            if (prices[i]>maxp) maxp=prices[i];
            else profit=max(profit,maxp-prices[i]);
            right.push_back(profit);
        }

        // combine the two vectors to find the split index s.t. profit is maximized
        for (int i=0; i<prices.size(); i++) {
            maxProfit=max(maxProfit, left[i]+right[prices.size()-i-1]);
        }
        return maxProfit;
    }
};