Best Time to Buy and Sell Stock II - Problem

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 sell and buy the stock multiple times on the same day, ensuring you never hold more than one share of the stock.

Find and return the maximum profit you can achieve.

Input & Output

Example 1 — Multiple Profitable Trades

$ Input: prices = [7,1,5,3,6,4]

› Output: 7

💡 Note: Buy on day 2 (price = 1), sell on day 3 (price = 5), profit = 4. Buy on day 4 (price = 3), sell on day 5 (price = 6), profit = 3. Total profit = 4 + 3 = 7.

Example 2 — Declining Prices

$ Input: prices = [7,6,4,3,1]

› Output: 0

💡 Note: Prices only decrease, so no profitable trades are possible. Maximum profit is 0.

Example 3 — Single Day

$ Input: prices = [1]

› Output: 0

💡 Note: Cannot make any trades with only one day of prices.

Constraints

1 ≤ prices.length ≤ 3 × 10⁴
0 ≤ prices[i] ≤ 10⁴

Visualization

Tap to expand

Asked in

a Amazon 85 G Google 70 M Microsoft 65 🍎 Apple 60

The key insight is that maximum profit equals the sum of all positive price differences between consecutive days. The greedy approach captures every upward price movement by adding profit whenever tomorrow's price exceeds today's price. Time: O(n), Space: O(1)

Common Approaches

✓ Brute Force - All Combinations

⏱️ Time: O(2ⁿ) Space: O(n)

Generate all possible ways to buy and sell stocks, considering multiple transactions, and find the combination that gives maximum profit.

Dynamic Programming - State Machine

⏱️ Time: O(n) Space: O(1)

Use dynamic programming with two states - holding a stock and not holding a stock. At each day, calculate the maximum profit for both states based on previous day's states.

Greedy - Capture Every Upward Movement

⏱️ Time: O(n) Space: O(1)

The key insight is that maximum profit equals the sum of all positive price differences between consecutive days. Buy before every price increase and sell before every price decrease.

Brute Force - All Combinations — Algorithm Steps

Generate all possible transaction sequences
Calculate profit for each sequence
Return maximum profit found

Visualization

Tap to expand

Step-by-Step Walkthrough

Decision Tree

Each day: buy, sell, or do nothing

Explore All Paths

Try every combination recursively

Maximum Profit

Return best profit from all paths

Code -

solution.c — C

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

int max(int a, int b) {
    return a > b ? a : b;
}

int dfs(int* prices, int n, int day, int holding, int profit) {
    if (day >= n) return profit;
    
    int maxProfit = dfs(prices, n, day + 1, holding, profit);
    
    if (holding) {
        maxProfit = max(maxProfit, dfs(prices, n, day + 1, 0, profit + prices[day]));
    } else {
        maxProfit = max(maxProfit, dfs(prices, n, day + 1, 1, profit - prices[day]));
    }
    
    return maxProfit;
}

int solution(int* prices, int n) {
    return dfs(prices, n, 0, 0, 0);
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    line[strcspn(line, "\n")] = 0;
    
    int prices[1000];
    int n = 0;
    char* token = strtok(line + 1, ",]");
    while (token != NULL) {
        prices[n++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    printf("%d\n", solution(prices, n));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(2ⁿ)

Each day we have 2 choices (buy/sell or not), leading to exponential combinations

✓ Linear Growth

Space Complexity

O(n)

Recursion stack depth for exploring all possibilities

⚡ Linearithmic Space

330.0K Views

High Frequency

~15 min Avg. Time

8.3K 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

Best Time to Buy and Sell Stock II - Problem

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - All Combinations — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler