package Greedy
import "math"
func maxProfit(prices []int) int {
return maxProfit2(prices)
}
func maxProfit1(prices []int) int {
minPrices := make([]int, len(prices))
minPrices[0] = prices[0]
for i := 1; i < len(prices); i++ {
minPrices[i] = min(minPrices[i-1], prices[i])
}
maxProfits := 0
for i := 0; i < len(prices); i++ {
maxProfits = max(maxProfits, prices[i]-minPrices[i])
}
return maxProfits
}
func maxProfit2(prices []int) int {
minPrices, maxProfits := math.MaxInt, math.MinInt
for i := 0; i < len(prices); i++ {
minPrices = min(minPrices, prices[i])
maxProfits = max(maxProfits, prices[i]-minPrices)
}
return maxProfits
}