-
Notifications
You must be signed in to change notification settings - Fork 1
/
stock.go
61 lines (56 loc) · 1.64 KB
/
stock.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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
package stock
import (
"math"
"github.com/catorpilor/leetcode/utils"
)
func Stock(prices []int) int {
n := len(prices)
if n <= 1 {
return 0
}
// k=2
// dp[i][j] represents at most i transactions, the max profit ending at day j (means selling at day j)
// dp[i][j] = max(dp[i][j-1], prices[j] - prices[m] + dp[i-1][m]) for m is [0.j-1]
// = max(dp[i][j-1], prices[j] + max(dp[i-1][j] - prices[j]))
// for example where i = 1, j = 2
// m = 0 prices[j] - prices[0] + dp[i-1][0]
// m = 1 prices[j] - prices[1] + dp[i-1][1]
// suppose maxdif for i = 1, j= 2 is on m = 1
// for i = 1 j = 3
// maxdif = utils.Max(maxdif, dp[i-1][j] - prices[j])
// dp[i][0] = 0 means at day 0 no profit
dp := make([][]int, 3)
for i := range dp {
dp[i] = make([]int, n)
}
for i := 1; i <= 2; i++ {
tempMax := dp[i-1][0] - prices[0]
for j := 1; j < n; j++ {
// for the original dp equation
// for m:=0; m<j;m++ {
// // there is a lot of re-compuate of max(dp[i-1][m]-prices[m])
// // so we use a temp var to store the max(dp[i-1][m] - prices[m]) we found so far when
// // iterate the prices array.
// dp[i][j] = utils.Max(dp[i][j], utils.Max(dp[i][j-1], prices[j]+dp[i-1][m]-prices[m]))
// }
dp[i][j] = utils.Max(dp[i][j-1], prices[j]+tempMax)
tempMax = utils.Max(tempMax, dp[i-1][j]-prices[j])
}
}
return dp[2][n-1]
}
func Stock2(prices []int) int {
n := len(prices)
if n <= 1 {
return 0
}
buy1, buy2 := math.MinInt32, math.MinInt32
sel1, sel2 := 0, 0
for _, p := range prices {
sel2 = utils.Max(sel2, buy2+p)
buy2 = utils.Max(buy2, sel1-p)
sel1 = utils.Max(sel1, buy1+p)
buy1 = utils.Max(buy1, -p)
}
return sel2
}