forked from spaghetti-source/algorithm
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathlongest_zigzag_subsequence.cc
More file actions
64 lines (59 loc) · 1.59 KB
/
longest_zigzag_subsequence.cc
File metadata and controls
64 lines (59 loc) · 1.59 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
//
// Longest ZigZag Subsequence
//
// Description:
//
// A sequence xs is zigzag if x[i] < x[i+1], x[i+1] > x[i+2], for all i
// (initial direction can be arbitrary). The maximum length zigzag
// subsequence is computed in O(n) time by a greedy method.
//
// First, we contract contiguous same numbers. Then, the number of
// peaks corresponds to the longest zig-zag subsequence.
//
#include <bits/stdc++.h>
using namespace std;
#define fst first
#define snd second
#define all(c) ((c).begin()), ((c).end())
#define TEST(s) if (!(s)) { cout << __LINE__ << " " << #s << endl; exit(-1); }
template <class T>
int longestZigZagSubsequence(vector<T> xs) {
int n = xs.size(), len = 1, prev = -1;
for (int i = 0, j; i < n; i = j) {
for (j = i+1; j < n && xs[i] == xs[j]; ++j);
if (j < n) {
int sign = (xs[i] < xs[j]);
if (prev != sign) ++len;
prev = sign;
}
}
return len;
}
// DP for verification
template <class T>
int longestZigZagSubsequenceN(vector<T> A) {
int n = A.size();
vector<vector<int>> Z(n, vector<int>(2));
Z[0][0] = 1;
Z[0][1] = 1;
int best = 1;
for(int i = 1; i < n; i++){
for(int j = i-1; j>= 0; j--){
if(A[j] < A[i]) Z[i][0] = max(Z[j][1]+1, Z[i][0]);
if(A[j] > A[i]) Z[i][1] = max(Z[j][0]+1, Z[i][1]);
}
best = max(best, max(Z[i][0],Z[i][1]));
}
return best;
}
int main() {
for (int seed = 0; seed < 10000; ++seed) {
srand(seed);
int n = 100;
vector<int> a(n);
for (int i = 0; i < n; ++i) {
a[i] = rand() % n;
}
assert(longestZigZagSubsequence(a) == longestZigZagSubsequenceN(a));
}
}