首页 > 代码库 > 编程之美2.16 最长递增子序列

编程之美2.16 最长递增子序列

      这道题目要求返回一个数字,这个数字代表一个数组中最长的递增子序列,当然,不要求这个序列是连续的,比如,有这样一个数组:{1, 3,5,7, 2, 9},那么这个数组的最长递增子序列就是5,即1,  3,  5,  7,9

      解决这道题目的思想就是:后面的数字只要是大于前面递增子序列的最大值,那么,它就一定大于前面所有的序列,既然需要知道前面保存的序列,那么,我们这里就需要一个辅助数组,数组中存储的就是“最小的连续递增子数组”,我们操作这个数组时,需要遵循两个规律:

      如果这个辅助数组为空,那么直接把原数组的数字放入其中

      1.如果原数组中的数字大于辅助数组的最大数字(即最后一个数字),那么,直接把原数组中的数放入其中就可以了,并把递增序列值加 1 

      2.如果原数组中的数字小于等于辅助数组的最大数字,那么,由于我们需要的是最小的连续递增子数组,所以,需要替换辅助数组中的值,这里,我们可以利用二分查找的办法(由于辅助数组是有序的),找到恰好比当前数字大的那个数字,替换掉就行了

     最后,返回辅助数组的长度就可以了:

     函数声明:

/*2.16 最长递增子序列*/
int DutBinFindForLRS(int*, int, int);
int DutLRS(int*, int);

      源代码:

/*二分查找*/
int DutBinFindForLRS(int* A, int size, int v)
{
	if (!A || size <= 0)
		return -1;

	int low = 0;
	int high = size - 1;

	while (low <= high)
	{
		int mid = low + (high - low) / 2;

		if (v >= A[mid])
			low = mid + 1;
		else
			high = mid - 1;
	}

	return low;
}

int DutLRS(int* A, int size)
{
	if (!A || size <= 0)
		return 0;

	int len = 1;
	int* tmp = new int[size];
	tmp[0] = A[0];

	for (int i = 1; i < size; ++i)
	{
		if (A[i] > tmp[len - 1])
			tmp[len++] = A[i];
		else
		{
			int pos = DutBinFindForLRS(tmp, len, A[i]);

			tmp[pos] = A[i];
		}
	}

	delete[] tmp;
	tmp = NULL;

	return len;
}


编程之美2.16 最长递增子序列