DSA · Greedy / Dynamic Programming · #38
Best Time to Buy and Sell Stock II
Module 46 · difficulty 3/5·⏱ 30:00starts on first keystroke
You are given an integer array `prices` where `prices[i]` is the price of a given stock on day `i`. On each day, you may decide to buy and/or sell the stock. You can hold **at most one** share of the stock at any time. However, you may buy it then immediately sell it on the **same day**. Find and return the **maximum profit** you can achieve. Implement the function `maxProfit(prices)` that returns the maximum profit as an integer.
Examples
prices = [7,1,5,3,6,4]→7— Buy on day 2 (price=1) and sell on day 3 (price=5), profit = 4. Then buy on day 4 (price=3) and sell on day 5 (price=6), profit = 3. Total = 7.prices = [1,2,3,4,5]→4— Buy on day 1 (price=1) and sell on day 5 (price=5), profit = 4. Equivalent to capturing every upward step.prices = [7,6,4,3,1]→0— Prices only decline, so no transaction is made and the max profit is 0.
Constraints
- · 1 <= prices.length <= 3 * 10^4
- · 0 <= prices[i] <= 10^4
Session phases
A · Clarify
B · Approach
C · Complexity
D · Edges
E · Code
F · Tradeoff
G · Score
Phase A — Clarify
Ask questions about input bounds, types, and edge constraints.
Ask the coach clarifying questions about the problem.
When you've covered this phase, advance to the next.