动态规划——最长非降子序列

该问题的思路及应用可参考动态规划——导弹拦截

Description

给定一个长度为N的整数数组, 请计算该数组中最长非降了序列长度。

Input

第一行输入M(M<=10)表示有M组数据。每组数据输入N(N<=10000), 接下来输入N个整数。

Output

输出M行正整数，第i行表示第i组数据的长非降了序列长度。

Sample Input

2
4 
1 3 2 4
9
4 1 7 3 2 3 5 7 6

Sample Output

3
5

注意非降！！！，而不是增长

#include<iostream>
using namespace std;
int main() {
	int T, N;                //T组，每组N个
	cin >> T;               //组数
	for (int i = 0; i < T; i++) {
		cin >> N;           //每组N个数


		//动态规划
		int* d= new int[N]; //d[i]表示第i个数之后序列的最长非降子序列长度（包括第i个）
		int* x = new int[N]; //x[i]表示第i个数

		for (int i = 0; i < N; i++) {
			cin >> x[i];
			d[i] = 1;     //d[i]初始化为1
			
		}
		for (int i = 0; i <N; i++) {  //从后向前，开始依次计算最长子序列（由已知推未知）
			for (int j =0; j < i; j++) {   //遍历i之前的所有值，确保i找到的是[0,i-1]中的的最长子序列
				if (x[i] >= x[j] && d[i] < d[j] + 1)
				{
					d[i] = d[j] + 1;
				}
				//如果第j个数小于第i个且d[i]>=d[j]+1，则d[i]=d[j]+1;依次向后循环，直到找到最大的d[j]+1，将其赋值为d(i)
			}
		}
		int max = 0;

		for (int i = 0; i < N; i++) {
			if (d[i] > max) { max = d[i]; }
		}
        	cout << max <<  endl;  //循环后d[0]对应的一定是其最长子序列
	}
	return 0;
}