We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Maximum Profit From Trading Stocks

Number: 2426

Difficulty: Medium

Paid? Yes

Companies: BlackRock, Oracle, Snowflake, Walmart Labs

Problem Description

You are given two 0-indexed integer arrays, present and future, where present[i] is the current price of the iᵗʰ stock and future[i] is its price a year later. You are also given an integer budget representing the money you have. You may purchase each stock at most once. The goal is to choose a subset of stocks to purchase such that the total cost does not exceed your budget and the profit (calculated as the sum of future prices minus the sum of purchase prices) is maximized.

Key Insights

  • Transform each stock into an item with a cost (present price) and a profit (future - present).
  • Only consider stocks that yield a positive profit, as buying a stock that doesn’t increase in value will not improve the overall profit.
  • This problem can be solved as a 0/1 Knapsack problem where:
    • Weight corresponds to the current price (cost).
    • Value corresponds to the profit (future - present).
  • Use dynamic programming to build up the maximum profit achievable given a sub-budget.

Space and Time Complexity

Time Complexity: O(n * budget) where n is the number of stocks.
Space Complexity: O(budget), using a 1D DP array.

Solution

We solve the problem using a dynamic programming approach similar to the 0/1 Knapsack problem. First, compute the profit for each stock as future[i] - present[i]. Only stocks with a positive profit are considered since others will not contribute to an increased profit. Then, initialize a DP array of size (budget + 1) where dp[b] represents the maximum profit with a budget b. For each valid stock, update the dp array in reverse order to ensure each stock is only used once. The answer is found in dp[budget].

Code Solutions

# Python solution for Maximum Profit From Trading Stocks

def maxProfit(present, future, budget):
    # Initialize dp array where dp[m] represents maximum profit with m budget
    dp = [0] * (budget + 1)
    
    # Iterate over each stock
    for i in range(len(present)):
        cost = present[i]
        profit = future[i] - present[i]
        # Only consider stocks that give a positive profit
        if profit > 0:
            # Traverse the dp array backwards to avoid using the same stock more than once
            for b in range(budget, cost - 1, -1):
                dp[b] = max(dp[b], dp[b - cost] + profit)
    
    # The maximum profit achievable with full budget is stored in dp[budget]
    return dp[budget]

# Example usage:
print(maxProfit([5,4,6,2,3], [8,5,4,3,5], 10))  # Expected output: 6
← Back to All Questions