Problem context and objectives
Mission briefing
Puzzle systems engineer · A game mechanic is behaving incorrectly
Collect every positive slope: The Rising Market.
Brute force may pass the demo but fail when the world fills with players.
How you win
- 1Recognize when Greedy stock transactions matches the clues
- 2Keep this true after every move: profit equals all positive price differences in the processed prefix
- 3Reach the result within O(n)
Rules and pressure
- Target cost: O(n)
- State rule: profit equals all positive price differences in the processed prefix
Lesson 1 of 3
Live algorithm trace
Greedy stock transactions
Complete execution1 of 6
Begin with no captured gains.
1
profit = 02
for each adjacent day pair3
gain = prices[i] - prices[i-1]4
if gain > 0: profit += gain5
return profitprofit = 0
Truth to preserve / Cost target
Truth to preserve
profit equals all positive price differences in the processed prefix
Cost target
O(n)
With unlimited nonoverlapping transactions, every upward day-to-day move can be collected. Combining adjacent gains or taking them separately gives the same profit.
Your call · What should guide every step of this algorithm?