Best Time to Buy and Sell Stock II - Practice Coding Problems

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

Understanding the Visualization

Input

Array of stock prices over consecutive days

Process

Identify all profitable buy-sell opportunities

Output

Maximum total profit from all transactions

Key Takeaway

🎯 Key Insight: Maximum profit is the sum of all profitable day-to-day price increases

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

Approach	Time	Space	Notes
✓ Brute Force - All Combinations	O(2ⁿ)	O(n)	Try all possible buy-sell transaction combinations
Dynamic Programming - State Machine	O(n)	O(1)	Track two states: holding stock and not holding stock
Greedy - Capture Every Upward Movement	O(n)	O(1)	Add profit whenever next day price is higher than current day

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

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - All Combinations — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler