C/C++教程

最长上升子序列 C++ 动态规划

本文主要是介绍最长上升子序列 C++ 动态规划，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！ 
#include<bits/stdc++.h>
using namespace std;
#define MAX 1010
int a[MAX];
int maxLen[MAX];//存储以数组的每一位为终点的最长子序列的长度，初始都为1
int main(){
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];//从i=1开始录入
		maxLen[i] = 1;//初始长度都为1
	}
	for (int i = 2; i <= n; i++) {
		//每次求的是以第i个数为终点的最长上升子序列的长度
		for (int j = 1; j < i; j++) {
			if (a[i] > a[j]) {
				//从i的后面察看以第j个数为终点的最长上升子序列
				maxLen[i] = max(maxLen[i], maxLen[j] + 1);
			}
		}

	}
	cout << *max_element(maxLen + 1, maxLen + n + 1);
	return 0;
}

这篇关于最长上升子序列 C++ 动态规划的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
您可能喜欢
栏目导航