122. Best Time to Buy and Sell Stock II

Problem description

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

Intuition:

The idea is to iterate through the array of stock prices and keep track of the minimum price seen so far and the maximum profit that can be achieved. We update these values as we traverse the array.

Approach:

Initialize variables max, min, and profit with the first element of the prices array.

Iterate through the prices array starting from the second element.

If the current price is less than the previous one, it indicates a potential sell point. Update the total profit by adding the current profit (max - min) to tprofit, reset max and min to the current price, and reset profit to 0.

If the current price is greater than the previous one, update max.

Update profit as the maximum of the current profit and max - min.

Finally, return the sum of tprofit and the last profit calculated.

Complexity Analysis:

Time Complexity: O(n) - where n is the length of the prices array. We iterate through the array only once.

Space Complexity: O(1) - Constant space is used.

Code


public class Solution {
    public int MaxProfit(int[] prices) {
        int max = prices[0];
        int min = prices[0];
        int profit = max - min;
        int n = prices.Length;
        int tprofit = 0;

        for(int i=1; i<n; i++) {
            if(prices[i] < prices[i-1]) {
                tprofit+=profit;
                max = prices[i];
                min = prices[i];
                profit = max - min;
            }
            if(prices[i] > prices[i-1]) {
                max = prices[i];
            }
            profit = Math.Max(profit, max-min);
        }
        return tprofit + profit;
    }
}