最长递增子序列

/*
 * 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;
}