Leetcode Study Day 5

Best Time to Buy and Sell Stock II

You are given an integer array prices where prices[i] is the price of a given stock on the ith day.

On each day, you may decide to buy and/or sell the stock. You can only hold at most one share of the stock at any time. However, you can buy it then immediately sell it on the same day.

Find and return the maximum profit you can achieve.

Example 1:

Input: prices = [7,1,5,3,6,4]
Output: 7
Explanation: Buy on day 2 (price = 1) and sell on day 3 (price = 5), profit = 5-1 = 4.
Then buy on day 4 (price = 3) and sell on day 5 (price = 6), profit = 6-3 = 3.
Total profit is 4 + 3 = 7.
Example 2:

Input: prices = [1,2,3,4,5]
Output: 4
Explanation: Buy on day 1 (price = 1) and sell on day 5 (price = 5), profit = 5-1 = 4.
Total profit is 4.
Example 3:

Input: prices = [7,6,4,3,1]
Output: 0
Explanation: There is no way to make a positive profit, so we never buy the stock to achieve the maximum profit of 0.
 

Constraints:

1 <= prices.length <= 3 * 104
0 <= prices[i] <= 104

Greedy solution

The greedy solution loop the whole array and compare the current elemnt to the previous element, if the current one is larger than the previous one, the difference between these two elemets is added to the maximum profits. It’s really a clever method that I can’t think by myself at the first time. The reason that we can use greedy solution is we only can hold one stock at a time and we can’t buy a stock before we sell the previous one.

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

Dynamic Programming

We can also solve it by using dynamic programming method, though it’s harder for me to understand.

First, we create two arrays, one is called withstock, which means we buy a stock; the other is called withoutstock, which means we sold a stock or we don’t have one.

vector<int> withstock (n,0);
vector<int> withoutstock (n,0);

Then we initialise the first value of these two arrays. The first element of withstock is 0 - prices[0] because we loose money for buying this stock. The first element of withoutstock is 0 because we don’t buy the first stock.

withstock[0] = -prices[0];
withoutstock[0] = 0;

Then we loop the prices array to update the value of withstock and withoutstock. During each iteration, we should find the best solution for each array. For example, for the array withstock, we should find the maximum value between the previous value in the withstock and the difference between the previous value of withoutstock and the price of this current element. It means we are comparing the money we get by don’t buying this current stock (element) or buying this one.

Similarly, for the withoutstock array, we decide whether we keep the stock we had or we sell it by finding the maximum value between withoutstock[i-1] and withstock[i-1] + prices[i]. Uhh, it’s do hard to explain it by words.

for (int i = 1; i < n; i++){
    withstock[i] = max(withstock[i - 1], (withoutstock[i-1] - prices[i]));
    withoutstock[i] = max(withoutstock[i-1], (withstock[i-1] + prices[i]));
}

Finally, we return the last element in the withoutstock array because we can’t have a stock at the end of the day.

Full code

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        if (n < 2){
            return 0;
        }
        vector<int> withstock (n,0);
        vector<int> withoutstock (n,0);
        withstock[0] = -prices[0];
        withoutstock[0] = 0;
        for (int i = 1; i < n; i++){
            withstock[i] = max(withstock[i - 1], (withoutstock[i-1] - prices[i]));
            withoutstock[i] = max(withoutstock[i-1], (withstock[i-1] + prices[i]));
        }
        return withoutstock[n-1];
    }
};