33 lines
723 B
Go
33 lines
723 B
Go
package q714
|
|
|
|
// Note: could be done faster with dynamic programming
|
|
|
|
func maxProfit(prices []int, fee int) int {
|
|
var low, high, profit int
|
|
bought := false
|
|
for i := range prices {
|
|
if bought {
|
|
high = max(high, prices[i])
|
|
if high-prices[i] > fee { // should have sold earlier or not bought
|
|
if high-low > fee {
|
|
profit += high - low - fee
|
|
}
|
|
bought = false
|
|
} else if prices[i] < low { // regret buying too early
|
|
low, high = prices[i], prices[i]
|
|
}
|
|
}
|
|
|
|
if !bought && i < len(prices)-1 && prices[i+1] > prices[i] {
|
|
bought = true // buy the dip
|
|
low, high = prices[i], prices[i]
|
|
}
|
|
}
|
|
|
|
if bought && high-low > fee {
|
|
profit += high - low - fee
|
|
}
|
|
return profit
|
|
}
|
|
|
|
var _ = maxProfit
|