Best Time to Buy and Sell Stock II - LeetCode

https://leetcode.com/problems/best-time-to-buy-and-sell-stock-ii/description/?envType=study-plan-v2&envId=top-interview-150

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

解析

按照上一个问题的解法，在原来的基础上多考虑一位，当发现下一位下降时就卖出然后买入，再次寻找。

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        min = prices[0]
        profit = 0
        if len(prices) == 2:
            if prices[0]<prices[1]:
                return prices[1] - prices[0]
            else:
                return 0
        for i in range(2, len(prices)):
            if prices[i-1] < min:
                min = prices[i-1]
            if prices[i-1] > min and prices[i] < prices[i-1]:
                profit += (prices[i-1] - min)
                min = prices[i]
            if i == len(prices)-1 and prices[-1] > min:
                profit += (prices[-1] - min)
        return profit

发现似乎将问题想复杂了。有一个关键的叙述是可以当天买进卖出。

Your approach seems reasonable but a bit more complicated than needed. When we can buy and sell on the same day, and there’s no cooldown period, we can simply go through the price array and whenever we see an increase from day i to day i+1, we can say we bought on day i and sold on day i+1. This will give us all the possible profit. So, the problem becomes simpler and we can solve it in a single pass.

Algorithm

• Initialize profit as 0.
• Loop through 1 to len(prices) - 1.
  • If prices[i] > prices[i-1], add prices[i] - prices[i-1] to profit.
• Return profit.

Explanation

• If the price of day i is greater than the price of day i-1, we make a profit by buying on day i-1 and selling on day i.
• The total profit will be the sum of all such profitable transactions.

Code

Here’s a simplified Python function:

def maxProfit(prices):
    profit = 0
    for i in range(1, len(prices)):
        if prices[i] > prices[i-1]:
            profit += prices[i] - prices[i-1]
    return profit

Example

• For prices = [7, 1, 5, 3, 6, 4]:
  • Buy on day 2 and sell on day 3: Profit = 4.
  • Buy on day 4 and sell on day 5: Profit = 3.
  • Total profit = 4 + 3 = 7.

This solution is efficient with a time complexity of (O(n)), where (n) is the length of the prices array. It uses a single loop to traverse through the array once and uses (O(1)) additional space to store the profit. It should work effectively even for large input sizes.

class Solution {
    public int maxProfit(int[] prices) {
        int profit = 0;
        for (int i = 1; i < prices.length; i++) {
            if (prices[i] > prices[i-1]){
                profit += (prices[i] - prices[i-1]);
            }
        }
        return profit;
    }
}

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