-
Notifications
You must be signed in to change notification settings - Fork 1
/
ws.go
119 lines (109 loc) · 3.01 KB
/
ws.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
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
package ws
import "github.com/catorpilor/leetcode/utils"
func WiggleMaxLength(nums []int) int {
n := len(nums)
if n < 2 {
return n
}
return 1 + utils.Max(helper(nums, 0, true), helper(nums, 0, false))
}
func helper(nums []int, idx int, flag bool) int {
var maxLen int
for i := idx + 1; i < len(nums); i++ {
if flag && nums[i] < nums[idx] || !flag && nums[i] > nums[idx] {
maxLen = utils.Max(maxLen, 1+helper(nums, i, !flag))
}
}
return maxLen
}
func WiggleMaxLengthDP1(nums []int) int {
n := len(nums)
if n < 2 {
return n
}
// up[i] refers to the length of the longest wiggle subsequence
// obtained so far considering element as the last element of the wiggle
// subsequence and ending with a rising wiggle.
// down[i] refers to the length of the longest wiggle subsequence
// obtained so far considering element as the last element of the wiggle
// subsequence and ending with a falling wiggle.
up, down := make([]int, n), make([]int, n)
for i := 1; i < n; i++ {
for j := 0; j < i; j++ {
if nums[j] < nums[i] {
up[i] = utils.Max(up[i], down[j]+1)
} else if nums[j] > nums[i] {
down[i] = utils.Max(down[i], up[j]+1)
}
}
}
return 1 + utils.Max(up[n-1], down[n-1])
}
func WiggleMaxLengthDP2(nums []int) int {
n := len(nums)
if n < 2 {
return n
}
// up[i] refers to the length of the longest wiggle subsequence
// obtained so far considering element as the last element of the wiggle
// subsequence and ending with a rising wiggle.
// down[i] refers to the length of the longest wiggle subsequence
// obtained so far considering element as the last element of the wiggle
// subsequence and ending with a falling wiggle.
up, down := make([]int, n), make([]int, n)
up[0], down[0] = 1, 1
// for every elemnt in nums it could be one of these three category.
// a. nums[i] > nums[i-1] means the rising wiggle, so the element before
// must be a falling position
// so we have up[i] = down[i-1]+1, down[i] = down[i-1]
// b. nums[i] < nums[i-1] similarly we can have
// down[i] = up[i-1]+1, up[i] = up[i-1]
// c nums[i] == nums[i-1]
// up[i] = up[i-1] down[i] = down[i-1]
for i := 1; i < n; i++ {
if nums[i] > nums[i-1] {
up[i], down[i] = down[i-1]+1, down[i-1]
} else if nums[i] < nums[i-1] {
down[i], up[i] = up[i-1]+1, up[i-1]
} else {
down[i], up[i] = down[i-1], up[i-1]
}
}
return utils.Max(up[n-1], down[n-1])
}
func WiggleMaxLengthDP3(nums []int) int {
// optimized space based on dp2
// case up[i], down[i] only related to up[i-1],down[i-1]
n := len(nums)
if n < 2 {
return n
}
up, down := 1, 1
for i := 1; i < n; i++ {
if nums[i] > nums[i-1] {
up = down + 1
} else if nums[i] < nums[i-1] {
down = up + 1
}
}
return utils.Max(up, down)
}
func WiggleMaxLengthGreedy(nums []int) int {
n := len(nums)
if n < 2 {
return n
}
prevDiff := nums[1] - nums[0]
ret := 1
if prevDiff != 0 {
ret = 2
}
for i := 2; i < n; i++ {
df := nums[i] - nums[i-1]
if prevDiff <= 0 && df > 0 || prevDiff >= 0 && df < 0 {
ret += 1
prevDiff = df
}
}
return ret
}