Maximum Profit From Trading Stocks - Video Solutions

Problem Overview: You are given two arrays: present and future. Buying stock i costs present[i] today and can be sold later for future[i]. With a limited budget, choose which stocks to buy to maximize total profit (future[i] - present[i]). Each stock can be purchased at most once.

The key observation: buying a stock only makes sense if it generates positive profit. After converting each stock into cost and profit, the problem becomes a classic 0/1 knapsack optimization.

Approach 1: Dynamic Programming (0/1 Knapsack) (Time: O(n * budget), Space: O(n * budget))

Treat each stock as an item where the weight is present[i] (the money spent) and the value is max(0, future[i] - present[i]) (the profit). Build a DP table dp[i][b] representing the maximum profit using the first i stocks with budget b. For every stock, decide whether to skip it or buy it if the remaining budget allows. The transition becomes dp[i][b] = max(dp[i-1][b], dp[i-1][b-present[i]] + profit). This approach explicitly models all choices and is easy to reason about when learning Dynamic Programming patterns.

Iteration runs through all stocks and every possible budget value, which results in O(n * budget) time. The full DP table stores states for each item and budget combination, requiring O(n * budget) memory.

Approach 2: Dynamic Programming (Space Optimization) (Time: O(n * budget), Space: O(budget))

The DP transition only depends on the previous row, so the 2D table can be compressed into a 1D array. Maintain dp[b] as the best profit achievable with budget b. For each stock, iterate the budget backwards from budget down to present[i]. Backward iteration prevents reusing the same stock multiple times, preserving the 0/1 constraint.

This reduces memory from O(n * budget) to O(budget) while keeping the same O(n * budget) runtime. The pattern appears frequently in problems that combine Array iteration with Dynamic Programming, especially knapsack-style optimizations.

Recommended for interviews: Start by explaining the knapsack transformation: cost equals purchase price and value equals profit. Interviewers expect the optimized 1D DP solution because it demonstrates strong understanding of state transitions and memory optimization. Mentioning the full 2D DP first shows you understand the recurrence before reducing space.