Greedy Merchant: Maximize Multi‑Product Profit in Limited Days

A merchant manages number different products, each with a maximum inventory limit item[index]. The price of each product on each day is given by item_price[item_index][day]. The goal is to compute the maximum total profit the merchant can obtain within days days, allowing unlimited buy‑sell cycles for each product.

Input

3          # number of products
3          # number of days
4 5 6      # maximum inventory for each product
1 2 3      # prices of product 1 over 3 days
4 3 2      # prices of product 2 over 3 days
1 5 3      # prices of product 3 over 3 days

Output

32         # maximum achievable profit

Explanation

Because trades of different products are independent, the total profit equals the sum of profits for each product. For a single product, the profit equals quantity × per‑unit profit. The per‑unit profit can be obtained by summing all positive day‑to‑day price differences, which is exactly the logic of LeetCode 122 (Best Time to Buy and Sell Stock II).

Product 1: buy 4 units at price 1 on day 1, sell at price 3 on day 3 → profit 8.

Product 2: no profitable transaction → profit 0.

Product 3: buy 6 units at price 1 on day 1, sell at price 5 on day 2 → profit 24.

Total profit = 8 + 24 = 32.

Solution Idea

For each product, compute the maximum profit of a single unit by iterating over the price list and adding every positive difference prices[i] - prices[i‑1]. Multiply this per‑unit profit by the product’s inventory limit and accumulate the result across all products.

Reference Implementation (Greedy)

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

n = int(input())
days = int(input())
numbers = list(map(int, input().split()))
ans = 0
for i in range(n):
    prices = list(map(int, input().split()))
    ans += maxProfit(prices, days) * numbers[i]
print(ans)

Complexity Analysis

Time complexity: O(N·M), where N is the number of products and M is the number of days, because each price list is scanned once. Space complexity: O(1), as only a few scalar variables are used.

Alternative DP Approach

A dynamic‑programming version can be written with the same time complexity but uses O(N) extra space to store intermediate states; the core logic remains identical to the greedy solution.