Repository navigation
Expand file tree
/
Copy path376-wiggle-subsequence.cpp
More file actions
98 lines (91 loc) · 2.81 KB
/
Copy path376-wiggle-subsequence.cpp
File metadata and controls
98 lines (91 loc) · 2.81 KB
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
//如果连续数字之间的差严格地在正数和负数之间交替,则数字序列称为 摆动序列 。第一个差(如果存在的话)可能是正数或负数。仅有一个元素或者含两个不等元素的序列也
//视作摆动序列。
//
//
// 例如, [1, 7, 4, 9, 2, 5] 是一个 摆动序列 ,因为差值 (6, -3, 5, -7, 3) 是正负交替出现的。
// 相反,[1, 4, 7, 2, 5] 和 [1, 7, 4, 5, 5] 不是摆动序列,第一个序列是因为它的前两个差值都是正数,第二个序列是因为它的最后一
//个差值为零。
//
//
// 子序列 可以通过从原始序列中删除一些(也可以不删除)元素来获得,剩下的元素保持其原始顺序。
//
// 给你一个整数数组 nums ,返回 nums 中作为 摆动序列 的 最长子序列的长度 。
//
//
//
// 示例 1:
//
//
//输入:nums = [1,7,4,9,2,5]
//输出:6
//解释:整个序列均为摆动序列,各元素之间的差值为 (6, -3, 5, -7, 3) 。
//
//
// 示例 2:
//
//
//输入:nums = [1,17,5,10,13,15,10,5,16,8]
//输出:7
//解释:这个序列包含几个长度为 7 摆动序列。
//其中一个是 [1, 17, 10, 13, 10, 16, 8] ,各元素之间的差值为 (16, -7, 3, -3, 6, -8) 。
//
//
// 示例 3:
//
//
//输入:nums = [1,2,3,4,5,6,7,8,9]
//输出:2
//
//
//
//
// 提示:
//
//
// 1 <= nums.length <= 1000
// 0 <= nums[i] <= 1000
//
//
//
//
// 进阶:你能否用 O(n) 时间复杂度完成此题?
//
// Related Topics 贪心 数组 动态规划 👍 979 👎 0
#include "headers.h"
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
public:
// 贪心算法
int wiggleMaxLength(vector<int> &nums) {
}
// 动态规划
int wiggleMaxLength2(vector<int> &nums) {
int n = nums.size();
vector<vector<int>> dp(n, vector<int>(2, 1));
// 1. dp[i][j]: 以 i 为截止的最长子序列, j=0: 前一个差值为负数, j=1: 前一个差值为正数
// 2. for(i: 1->n-1)
// for(j: 0->i-1)
// if (nums[i] > nums[j])
// dp[i][1] = max(dp[i][1], dp[j][0] + 1);
// else if (nums[i] < nums[j])
// dp[i][0] = max(dp[i][0], dp[j][1] + 1);
int res = 1;
for (int i = 1; i < n; ++i) {
for (int j = 0; j < i; ++j) {
if (nums[i] > nums[j])
dp[i][1] = max(dp[i][1], dp[j][0] + 1);
else if (nums[i] < nums[j])
dp[i][0] = max(dp[i][0], dp[j][1] + 1);
}
res = max(res, max(dp[i][0], dp[i][1]));
}
showVector2(dp);
return res;
}
};
//leetcode submit region end(Prohibit modification and deletion)
int main() {
Solution s;
vector<int> arr{1, 7, 4, 9, 2, 5};
assert(s.wiggleMaxLength(arr) == 6);
}