-
LCS
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
40int** (string x, string y) {
int m = x.size();
int y = y.size();
int** c = new int* [m + 1];
for (int i = 0; i < m + 1; ++i) {
c[i] = new int[n + 1];
}
for (int i = 0; i < m + 1; ++i)
c[i][0] = 0;
for (int i = 0; i < n + 1; ++i)
c[0][i] = 0;
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if ( x[i] == y[j] ) {
c[i+1][j+1] = c[i][j] + 1;
}
else {
c[i+1][j+1] = (c[i+1][j] > c[i][j+1]) ? c[i+1][j] : c[i][j+1];
}
}
}
// reconstruct the LCS
string temp;
while (c[m][n]) {
if (x[m - 1] == y[n - 1]) {
temp += x[m - 1];
--m;
--n;
}
else {
if (c[m - 1][n] > c[m][n - 1])
--m;
else
--n;
}
}
reverse(temp.begin(), temp.end());
return c;
} -
Longest Increasing Subsequence
-
O(n^2)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17int LIS(vector<int> a) { // res[i] : LIS(0, i) contains a[i]
int max = 0;
int len = a.size();
int* res = new int[len];
res[0] = 1;
for (int i = 1; i < len; ++i) {
for (int j = 0; j < i; ++j) {
max = (a[j] < a[i] && res[j] > max) ? res[j] : max;
}
res[i] = max + 1;
max = 0;
}
for (int i = 0; i < len; ++i)
max = res[i] > max ? res[i] : max;
delete [] res;
return max;
} -
O(nlogn)
1
2
3
4
5
6
7
8
9
10
11
12
13int LIS(vector<int> v) { // how to reconstrcut the lis
int len = v.size();
vector<int> res;
vector<int>::iterator iter;
for (int i = 0; i < len; ++i) {
iter = lower_bound(res.begin(), res.end(), v[i]);
if (iter != res.end())
*iter = v[i];
else
res.push_back(v[i]);
}
return res.size();
}
-
近期评论