/* * MaxIncresingSubSequeuce.cpp * * Created on: 2012-6-24 * Author: jiyiqin * * 最长递增子序列,比如1,-1,2,-3,4,-2,6,-5, 返回 1,2,4,6,长度为4 * */ #include <iostream> using namespace std; class MaxIncresingSubSequence{ public: /** * 动态规划: * 求解a[0...i]的最长递增子序列的问题可以转换成求解a[0...i-1]的最长递增子序列的问题 * 我们将LIS[i]表示以a[i]结尾的最长递增子序列的长度 * * 那么在求解LIS[i]的时候,就会想到如果a[i]大于a[0...i-1]的最长递增子序列的最大元素的话, * 那么就将a[i]算进去,如果不是,则看其他子序列有没有最大元素比a[i]小的,将a[i]算到该序列中去。 * * LIS[i] = max{LIS[k] + 1, 1}, 其中0<=k<i. * 要么加到某个子序列中,要么自己组成一个新的子序列(最小元素) * */ static void m_subSequence(int a[], int size){ /* 将所有元素的最长递增子序列长度初始化为1 */ int *lis = new int[size]; for(int i=0;i<size;i++){ lis[i] = 1; } /* 以a[i]的索引i作为循环索引 */ for(i=0;i<size;i++){ /* 从前面已经求出的lis值里面找一个最大元素比我小,并且长度最长的 */ for(int j=0;j<i;j++){ if(a[j] < a[i] && ((lis[j] + 1) > lis[i])){ lis[i] = lis[j] + 1; } } } /* 输出以所有元素结尾的最长递增子序列长度 */ for(i=0;i<size;i++){ cout<<lis[i]<<" "; } cout<<endl; /** * 优化:每次求解LIS[i]的时候,往前寻找满足条件(尾部小于a[i],长度更新后更大)的子序列都是 * 顺序扫描,其实我们可以快速找到满足条件的那些LIS[k],比如对LIS[]排序。 * 申明一个数组maxV[],maxValue[i]表示长度为i的递增子序列的尾部的值。 * */ } static void testLIS(){ int a[10] = {1,-1,2,-3,4,-2,6,-5,10,3}; m_subSequence(a, 10); } }; int main(){ MaxIncresingSubSequence::testLIS(); return 0; }