[算法设计]求最长子序列问题

问题: 求无序序列的最长子序列

方法: 动态规划法

关键点:

dp[i] : 表示数组中的第i位置的最长子序列的长度,初始默认所有位置的dp[i] = 1

思路: 假设已知Subsequence[i-1]位置的最长子序列为dp[i-1],则dp[i],显然如果subsequence[i]>subsequence[i-1],则dp[i] = dp[i-1] + 1

代码:

#include <cstdio>
#include <algorithm>
using namespace std;
/*求最长子序列*/

int main() {
	const int MaxN = 100;
	int Subsequence[MaxN];
	int dp[MaxN];
	for (int j = 0; j < MaxN; ++j) {
		dp[j] = 1;
	}
	int n;
	scanf_s("%d", &n);
	if (n != 0) {
		for (int i = 0; i < n; ++i) {
			scanf_s("%d", &Subsequence[i]); //子序
		}
		for (int i = 0; i < n; ++i) {
			for (int j = 0; j < i; ++j) {
				if (Subsequence[i] > Subsequence[j]) {
					dp[i] = max(dp[j] + 1, dp[i]);
				}
			}
		}                                    
		printf("输入结束!\n");
		for (int j = 0; j < n; ++j) {
			printf("%d", Subsequence[j]);
		}
		printf("\n");
		for (int j = 0; j < n; ++j) {
			printf("%d", dp[j]);
		}
	}
	return 0;
}