第四十七题（求最长递减子序列）

本文主要是介绍第四十七题（求最长递减子序列），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目：

求一个数组的最长递减子序列比如{9，4，3，2，5，4，3，2}的最长递减子序列为{9，5，4，3，2}

动态规划经典题目。

c++代码：

#include<iostream>
using namespace std;
namespace MS100P_47
{/*求一个数组的最长递减子序列比如{9，4，3，2，5，4，3，2}的最长递减子序列为{9，5，4，3，2}*/void  printArray(int dp[], int data[], int k)	 {for (int i = k - 1; i>=0;i--)if (dp[i] == dp[k] - 1 && data[k] < data[i])printArray(dp, data, i);cout << data[k] << ' ';}int  findDecrease(int data[], int length){int* dp = new int[length];//length[i]表示数组下标i之前元素的最长递减子序列的长度int max = 0;dp[0] = 1;for (int i = 1; i <length; i++){dp[i] = 1;for (int j = 0; j < i; j++){if (data[i] < data[j]&&dp[j]+1>dp[i])dp[i] = dp[j] + 1;}}int maxIndex;for (int i = length; i >0; i--)if (max < dp[i]){max = dp[i];maxIndex = i;}printArray(dp, data, maxIndex);delete[]dp;return max;}void test(){int data[] = { 9,4,3,2,5,4,3,2 };int n=findDecrease(data, 8);cout << endl << "长度为：" << endl;cout << n << endl;}
}
int _tmain(int argc, _TCHAR* argv[])
{MS100P_47::test();return 0;
}

运行结果：

这篇关于第四十七题（求最长递减子序列）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---