Best Time to Buy and Sell Stock

1. Problem Description

Given an array prices, where prices[i] is the price of a stock on day i.

You may choose one day to buy the stock and a different future day to sell it. Design an algorithm to compute the maximum profit you can obtain.

Return the maximum profit from this transaction. If no profit can be made, return 0.

2. Approach

1. Approach 1
   • Brute force
   • Choose a buy day, then scan later sell days and find the largest difference
2. Approach 2
   • Maximum profit = selling price - minimum buying price
   • Track the minimum buying price while traversing, and compute the possible profit at each selling price

3. Implementation

3.1. Brute Force

func maxProfit(prices []int) int {
	if len(prices) == 0 {
		return 0
	}

	max := 0
	for i := 0; i < len(prices)-1; i++ {
		buy := prices[i]
		for j := i + 1; j < len(prices); j++ {
			sell := prices[j]
			max = Max(max, sell-buy)
		}
	}

	return max
}

func Max(data ...int) int {
	max := data[0]
	for i := 1; i < len(data); i++ {
		if data[i] > max {
			max = data[i]
		}
	}
	return max
}

3.2. Minimum Value

func maxProfit(prices []int) int {
    minPrice := math.MaxInt32
    maxProfit := 0
    for _, price := range prices {
        minPrice = min(minPrice, price)
        maxProfit = max(maxProfit, price- minPrice)
    }
    return maxProfit
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

func max(a, b int) int {
    if a < b {
        return b
    }
    return a
}

4. References

• 121. Best Time to Buy and Sell Stock - LeetCode