Maximum Profit From Trading Stocks - Practice Coding Problems

Maximum Profit From Trading Stocks - Problem

You are given two 0-indexed integer arrays of the same length present and future where present[i] is the current price of the i-th stock and future[i] is the price of the i-th stock a year in the future.

You may buy each stock at most once. You are also given an integer budget representing the amount of money you currently have.

Return the maximum amount of profit you can make.

Input & Output

Example 1 — Basic Case

$ Input: present = [5,3,4], future = [10,8,6], budget = 8

› Output: 10

💡 Note: Buy stocks 0 and 1: cost = 5+3 = 8 ≤ budget, profit = (10-5) + (8-3) = 5 + 5 = 10. Stock 2 gives profit 6-4 = 2, but we can't afford all three.

Example 2 — Limited Budget

$ Input: present = [1,2,3], future = [3,5,4], budget = 3

› Output: 5

💡 Note: Buy stocks 0 and 1: cost = 1+2 = 3 ≤ budget, profit = (3-1) + (5-2) = 2 + 3 = 5. This gives maximum profit within budget.

Example 3 — No Profitable Stocks

$ Input: present = [5,4,3], future = [3,2,1], budget = 10

› Output: 0

💡 Note: All stocks lose money (future < present), so we don't buy any stock and profit = 0.

Constraints

1 ≤ present.length, future.length ≤ 1000
present.length == future.length
0 ≤ present[i], future[i] ≤ 1000
0 ≤ budget ≤ 1000

Visualization

Tap to expand

Understanding the Visualization

Input

Present prices [5,3,4], Future prices [10,8,6], Budget: 8

Process

Calculate profits [5,5,2] and find optimal combination

Output

Buy stocks 0,1 for maximum profit: 10

Key Takeaway

🎯 Key Insight: This is a 0/1 knapsack problem - use dynamic programming to find optimal stock combination within budget

Asked in

GS Goldman Sachs 25 MS Morgan Stanley 20 a Amazon 15 G Google 12

This is a 0/1 knapsack problem where we want to maximize profit while staying within budget. The optimal approach uses dynamic programming with time O(n × budget) and space O(budget). Key insight: only consider profitable stocks and use DP to find the best combination.

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Try All Combinations	O(2^n)	O(n)	Generate all possible subsets and find the one with maximum profit within budget
Dynamic Programming - Knapsack	O(n × budget)	O(budget)	Use 0/1 knapsack DP to find optimal combination of stocks within budget
Greedy - Sort by Profit Ratio	O(n log n)	O(n)	Sort stocks by profit-to-cost ratio and greedily select the most efficient ones

Brute Force - Try All Combinations — Algorithm Steps

Step 1: Generate all possible combinations of stocks (2^n subsets)
Step 2: For each combination, check if total cost ≤ budget
Step 3: Calculate profit for valid combinations and track maximum

Visualization

Tap to expand

Step-by-Step Walkthrough

Generate Subsets

Create all 2^n combinations using bit manipulation

Check Budget

Calculate total cost and verify it's within budget

Find Maximum

Track the combination with highest profit

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int solution(int* present, int* future, int n, int budget) {
    int maxProfit = 0;
    
    // Try all 2^n combinations
    for (int mask = 0; mask < (1 << n); mask++) {
        int totalCost = 0;
        int totalProfit = 0;
        
        for (int i = 0; i < n; i++) {
            if (mask & (1 << i)) {
                totalCost += present[i];
                int profit = future[i] - present[i];
                if (profit > 0) {
                    totalProfit += profit;
                }
            }
        }
        
        if (totalCost <= budget && totalProfit > maxProfit) {
            maxProfit = totalProfit;
        }
    }
    
    return maxProfit;
}

int main() {
    char line[1000];
    int present[20], future[20], n = 0;
    
    // Parse present array
    fgets(line, sizeof(line), stdin);
    char* token = strtok(line, "[,]");
    while (token != NULL) {
        present[n] = atoi(token);
        token = strtok(NULL, "[,]");
        n++;
    }
    
    // Parse future array
    fgets(line, sizeof(line), stdin);
    token = strtok(line, "[,]");
    int idx = 0;
    while (token != NULL && idx < n) {
        future[idx] = atoi(token);
        token = strtok(NULL, "[,]");
        idx++;
    }
    
    // Parse budget
    fgets(line, sizeof(line), stdin);
    int budget = atoi(line);
    
    printf("%d\n", solution(present, future, n, budget));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(2^n)

We generate all 2^n possible subsets of stocks

⚠ Quadratic Growth

Space Complexity

O(n)

Recursion stack depth up to n levels

⚡ Linearithmic Space

23.5K Views

Medium Frequency

~25 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Try All Combinations — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler