Buy Maximum Stocks if i Stocks Buyable on Day i

Buy Maximum Stocks if i Stocks Buyable on Day i is a clean greedy problem. It teaches a core habit: when you want the most items for a fixed budget, spend on the cheapest first.

The slow way first

You might try every combination of how many shares to take from each day and keep the best total within budget. With many days that explodes combinatorially — far too slow, and there is no obvious recurrence to memoize cleanly.

The question to ask: to maximize the share count, which dollar should I spend next? The dollar that buys the most shares — that is, the one spent on the cheapest stock. That hint points straight at a greedy strategy.

The idea: cheapest price first

Pair each price with its day limit, then sort the pairs by price. Walk the sorted list cheapest-first. For each stock, buy as many shares as you can afford and the day limit allows: qty = min(limit, budget // price). Subtract the cost, add to the running count, and move to the next-cheapest stock.

Why is greedy correct? Spending a dollar on a cheaper share always yields at least as many shares as spending it on a costlier one, and the day limit only caps each stock independently. So exhausting the cheapest first can never be beaten.

Walk through it

Step through the animation. The pairs are already sorted by price: 7, 10, 19 with limits 2, 1, 3. The buy pointer moves cheapest-to-costliest. At each stock we take min(limit, budget // price) shares, watch the budget shrink, and watch the bought count climb to 4.

Pseudocode

pair each price with its day limit
sort the pairs by price (cheapest first)
bought = 0
for each (price, limit) in the sorted pairs:
    qty = min(limit, budget // price)   # afford-able and allowed
    bought = bought + qty
    budget = budget - qty * price       # pay for them
return bought

The Python solution

def max_stocks(price, day_limit, budget):
    stocks = list(zip(price, day_limit))
    stocks.sort()
    bought = 0
    for p, limit in stocks:
        qty = min(limit, budget // p)
        bought += qty
        budget -= qty * p
    return bought

• zip(price, day_limit) builds the (price, limit) pairs; sorting a list of tuples sorts by the first field, the price.
• bought accumulates the total number of shares.
• qty = min(limit, budget // p) is the heart of the greedy step: budget // p is how many we can afford, limit is how many we are allowed that day, and we take the smaller.
• budget -= qty * p pays for those shares so later stocks see the reduced budget.
• We return bought once every pair has been considered.

Complexity

The sort is the bottleneck at O(n log n); the buying sweep is a single linear pass. The extra O(n) space holds the paired list.

When this pattern shows up

Practice