3573. Best Time to Buy and Sell Stock V

Time: O(n * k)

Space: O(k)

Approach

DP tracking buy/sell states with at most k transactions and cooldown constraints.

Key Techniques

Array problems involve manipulating elements stored in a contiguous block of memory. Key techniques include two-pointer traversal, prefix sums, sliding windows, and in-place partitioning. In C#, arrays are zero-indexed and fixed in size — use List<T> when you need dynamic resizing.

Dynamic Programming

Dynamic programming solves problems by breaking them into overlapping sub-problems and storing results to avoid redundant work. The key steps are: define state, write a recurrence relation, set base cases, and choose top-down (memoization) or bottom-up (tabulation). DP often yields O(n²) → O(n) time improvements over brute force.

3573.cs

// Approach: DP tracking buy/sell states with at most k transactions and cooldown constraints.
// Time: O(n * k) Space: O(k)

public class Solution
{
    public long MaximumProfit(int[] prices, int k)
    {
        int n = prices.Length;
        long[] prev = new long[n];
        long[] curr = new long[n];
        for (int t = 1; t <= k; t++)
        {
            long bestLong = -prices[0];
            long bestShort = prices[0];
            curr[0] = 0;
            for (int i = 1; i < n; i++)
            {
                long res = curr[i - 1];
                res = Math.Max(res, prices[i] + bestLong);
                res = Math.Max(res, -prices[i] + bestShort);
                curr[i] = res;
                bestLong = Math.Max(bestLong, prev[i - 1] - prices[i]);
                bestShort = Math.Max(bestShort, prev[i - 1] + prices[i]);
            }
            
            var tmp = prev;
            prev = curr;
            curr = tmp;
        }

        return prev[n - 1];
    }
}

Was this solution helpful?