How to Maximize Mooncake Profit: Brute Force, Greedy, and DP Solutions

Story Origin

As the Mid‑Autumn Festival approaches, the author noticed mooncake prices on the internal company platform jumping from 78 to 150 within days, sparking curiosity about the best buy‑sell timing for such price fluctuations.

Input and Output

The daily mooncake prices are given as an array, and the task is to output the maximum possible profit.

Example input: [7, 1, 5, 3, 6, 4] Output: 5 (buy on day 2 at price 1, sell on day 5 at price 6).

Brute‑Force Method

Enumerate every pair of days, compute the price difference, and keep the maximum. This straightforward approach has O(N²) time complexity and may time‑out on large datasets.

func maxProfit(prices []int) int {
    var result int
    for i := 1; i < len(prices); i++ {
        for j := 0; j < i; j++ {
            result = max(result, prices[i]-prices[j])
        }
    }
    return result
}

Greedy Algorithm

Maintain the lowest price seen so far while scanning the array; the profit on each day is the current price minus this minimum. Update the maximum profit accordingly. This runs in O(N) time.

func maxProfit(prices []int) int {
    var minPrice = prices[0]
    var result int
    for i := 1; i < len(prices); i++ {
        minPrice = min(minPrice, prices[i])
        diff := prices[i] - minPrice
        result = max(result, diff)
    }
    return result
}

Dynamic Programming

The problem can also be viewed as finding the maximum sum of a contiguous increasing subsequence. Define dp[i] as the maximum profit ending at day i; update it using the previous day's dp value and the price difference.

func maxProfit(prices []int) int {
    var dp = make([]int, len(prices))
    var result int
    for i := 1; i < len(prices); i++ {
        diff := prices[i] - prices[i-1]
        dp[i] = max(dp[i-1]+diff, 0)
        if dp[i] > result {
            result = dp[i]
        }
    }
    return result
}

Conclusion

All three methods are common and important for algorithmic problems. Brute force helps clarify the idea, greedy offers an optimal linear solution, and dynamic programming provides an iterative perspective useful for related challenges. Happy coding and enjoy your mooncakes!