-
Notifications
You must be signed in to change notification settings - Fork 1
/
max_profit.go
42 lines (36 loc) · 894 Bytes
/
max_profit.go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
package _123_best_time_to_buy_and_sell_stock_III
func maxProfit(prices []int) int {
if len(prices) <= 1 {
return 0
}
start := make([]int, len(prices))
minPrice, maxProfit := prices[0], 0
for i := 1; i < len(prices); i++ {
if prices[i] < minPrice {
minPrice = prices[i]
} else if profit := prices[i] - minPrice; profit > maxProfit {
maxProfit = profit
}
start[i] = maxProfit
}
if len(prices) < 4 {
return maxProfit
}
result := maxProfit
end := make([]int, len(prices))
maxPrice, maxProfit := prices[len(prices)-1], 0
for i := len(prices) - 1; i >= 0; i-- {
if prices[i] > maxPrice {
maxPrice = prices[i]
} else if profit := maxPrice - prices[i]; profit > maxProfit {
maxProfit = profit
}
end[i] = maxProfit
}
for i := 1; i < len(prices)-2; i++ {
if profit := start[i] + end[i+1]; profit > result {
result = profit
}
}
return result
}