Best Time to Buy and Sell Stock II

Medium
81.

Best Time to Buy and Sell Stock II

Best Time to Buy and Sell Stock II is a medium coding problem on arrays, dynamic programming and greedy, asked in Directi interviews.

You are given prices where prices[i] is a stock's price on day i. You may buy and sell on the same day, holding at most one share at a time, with unlimited transactions.

Return the maximum total profit.

Example 1

Input
prices = [7,1,5,3,6,4]
Output
7
Explanation
Buy day 2, sell day 3 (+4); buy day 4, sell day 5 (+3).

Example 2

Input
prices = [1,2,3,4,5]
Output
4

Example 3

Input
prices = [7,6,4,3,1]
Output
0

Constraints

  • 1 <= prices.length <= 30
  • 0 <= prices[i] <= 1000
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function(prices) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Best Time to Buy and Sell Stock II — Problem & Solution

Best Time to Buy and Sell Stock II solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Best Time to Buy and Sell Stock II is a medium coding problem on arrays, dynamic programming and greedy, asked in Directi interviews.

  • Difficulty: Medium
  • Topics: Arrays, Dynamic Programming, Greedy
  • Asked at: Directi
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

You are given prices where prices[i] is a stock's price on day i. You may buy and sell on the same day, holding at most one share at a time, with unlimited transactions.

Return the maximum total profit.

Example 1

Input: prices = [7,1,5,3,6,4]
Output: 7
Explanation: Buy day 2, sell day 3 (+4); buy day 4, sell day 5 (+3).

Example 2

Input: prices = [1,2,3,4,5]
Output: 4

Example 3

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

Constraints

  • 1 <= prices.length <= 30
  • 0 <= prices[i] <= 1000

Hints for Best Time to Buy and Sell Stock II

  1. Hint 1

    Every upward price movement can be captured independently.

  2. Hint 2

    Sum all positive day-to-day differences.

How to solve Best Time to Buy and Sell Stock II

With unlimited transactions and same-day trading allowed, there is nothing to plan. Any profitable multi-day hold can be split into its individual daily moves without losing a penny, so the best possible total is simply the sum of every upward step in the price series.

Approach

  1. Walk the prices from the second day onwards.
  2. If today's price is higher than yesterday's, add the difference to the total.
  3. Ignore every day where the price fell or stayed flat.
  4. The accumulated total is the maximum profit.

Why it works

Two directions. It is achievable: buying at the start of every rising run and selling at its top yields exactly the sum of the positive steps, since a hold from i to j earns prices[j] - prices[i], which telescopes into the daily differences along the way. It is also an upper bound: any set of non-overlapping holds earns the sum of its own telescoped differences, and each of those is at most the sum of the positive steps it covers, because the negative steps only subtract. So the two meet.

Complexity

  • Time — O(n)
  • Space — O(1)

Pitfalls

  • Do not try to find the global minimum and maximum — that solves the single-transaction problem and undercounts here.
  • A strictly falling series earns 0, not a negative number: only positive differences are added.
  • Flat days contribute nothing, so > versus >= makes no difference to the total.

Reference solution

Python

from typing import List

def maxProfit(prices: List[int]) -> int:
    profit = 0
    for i in range(1, len(prices)):
        if prices[i] > prices[i - 1]:
            profit += prices[i] - prices[i - 1]
    return profit

Java

public static int maxProfit(int[] prices) {
    int total = 0;
    for (int i = 1; i < prices.length; i++) {
        if (prices[i] > prices[i - 1]) total += prices[i] - prices[i - 1];
    }
    return total;
}

C++

int maxProfit(vector<int>& prices) {
    int total = 0;
    for (int i = 1; i < (int) prices.size(); i++) {
        if (prices[i] > prices[i - 1]) total += prices[i] - prices[i - 1];
    }
    return total;
}

JavaScript

var maxProfit = function(prices) {
    let profit = 0;
    for (let i = 1; i < prices.length; i++) {
        if (prices[i] > prices[i - 1]) profit += prices[i] - prices[i - 1];
    }
    return profit;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Dynamic Programming