这篇文章主要介绍了C++计算整数序列的最长递增子序列的长度操作，具有很好的参考价值，希望对大家有所帮助。一起跟随小编过来看看吧
给定一个整数序列，计算其中的最长递增子序列的长度，这是一个典型的动态规划的算法。
比如8个整数的序列 186 186 150 200 160 130 197 200，最长递增子序列是 150 160 197 200, 长度为4。
想要解决此问题，可以把这个大问题分解为小问题，依次考虑每个数，计算出包含该数数和该数之前的所有数的最长递增子序列的长度，计算出的长度值作为该数的对应值记录下来，最后可以得到这8个数对应的长度值序列，也是8个数，找到这8个数中的最大值就是所有书的最长递增子序列的长度。
或者也可以这样想，想要计算8个数的最长递增子序列的长度有难度，不如先考虑最简单的情况。只有一个数的时候，最长递增子序列长度就是1；当有两个数时，只考虑第一个数和它以前的数的最长递增子序列就是1，考虑第二个数时只需要找到它之前的所有数中比第二个数小的所有数中最长递增子序列的长度最大值然后加一 ，就是第二个数的长度。
下面给出实现代码：
#include #include #include using namespace std; int findLoogestIncreaseSeq(vector &vect) { int len = 0; int *count = new int[vect.size()]; for (int i = 0; i <vect.size(); i++) count[i] = 1; for (int i = 0; i = 0; j--) { if (vect[j] = count[i]) { count[i] = count[j] + 1; } } if (count[i] > len) len = count[i]; } delete [] count; return len; } int main() { vector vect; int temp; while (cin >> temp) { vect.push_back(temp); } cout << findLoogestIncreaseSeq(vect) << endl; return 0; }
补充知识：C++ 求最长递增子序列（动态规划）
| i | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
| a[i] | 1 | 4 | 7 | 2 | 5 | 8 | 3 | 6 | 9 |
| lis[i] | 1 | 2 | 3 | 2 | 3 | 4 | 3 | 4 | 5 |
时间复杂度为n^2的算法：
//求最长递增子序列 //2019/2/28 #include using namespace std; int LIS(int a[],int N) { int lis[100] = {}; for(int i =0;i<N;i++)//给每一个数的lis赋初值为1 { lis[i]=1; } for(int i = 1;i<N;i++) { for(int j =0;j<i>>N) { for(int i = 0;i<i style="color:transparent">来源gaodai$ma#com搞$代*码*网</i>>a[i]; cout<<LIS(a,N)<<endl; } return 0; }
以上这篇C++计算整数序列的最长递增子序列的长度操作就是小编分享给大家的全部内容了，希望能给大家一个参考，也希望大家多多支持gaodaima搞代码网。
以上就是C++计算整数序列的最长递增子序列的长度操作的详细内容，更多请关注gaodaima搞代码网其它相关文章！
搞代码网（gaodaima.com）提供的所有资源部分来自互联网，如果有侵犯您的版权或其他权益，请说明详细缘由并提供版权或权益证明然后发送到邮箱[email protected]，我们会在看到邮件的第一时间内为您处理，或直接联系QQ：872152909。本网站采用BY-NC-SA协议进行授权
转载请注明原文链接：C++计算整数序列的最长递增子序列的长度操作
转载请注明原文链接：C++计算整数序列的最长递增子序列的长度操作
