动态规划求最长下降子序列和最长上升子序列

#include <bits/stdc++.h>
using namespace std;

const int N = 30000 + 10;

int a[N], f1[N], f2[N];
int res1, res2;

int main() {

	int n = 1;
	while (cin >> a[n]) {
		n++;
	}
	for (int i = 1; i <= n - 1; i++) {
		f1[i] = 1, f2[i] = 1;
		for (int j = 1; j < i; j++) {
			if (a[i] <= a[j])//最长下降子序列
				f1[i] = max(f1[i], f1[j] + 1);

			if (a[i] > a[j])//最长上升子序列
				f2[i] = max(f2[i], f2[j] + 1);

		}
		res1 = max(res1, f1[i]);
		res2 = max(res2, f2[i]);
	}

	cout << res1 << endl << res2;
}

解题思路:

注意事项:

参考代码: