学步园

题目来自编程之美

题目

思路(1) 动态规划(复杂度为n^2)

方程：

F[i]:表示以nArr[i]为结尾的最长递增子序列的最大长度。
F[i] = Max(F[j]) + 1 && a[i] > a[j] && i > j;

方程的直观含义：检查nArr[i]能接在哪一个数的后面。

如果要求LIS序列，需要令开辟一个数组。

复杂度：O(n^2)

代码:只求LIS的长度

#include <iostream>
#include <assert.h>
using namespace std;

/*
F[i]:表示以nArr[i]为结尾的最长递增子序列的长度
F[i] = Max(F[j]) + 1 && a[i] > a[j] && i > j;
F[i] = 1
*/
int LIS(int nArr[],int nLen)
{
	int nMaxLen = 1;
	int* F = new int[nLen];
	//递推
	for (int i = 1;i < nLen;i++)
	{
		F[i] = 1;
		for (int j = i - 1;j >= 0;j--)
		{
			if (nArr[i] > nArr[j])
			{
				F[i] = max(F[i],F[j] + 1);
			}
		}
		nMaxLen = max(nMaxLen,F[i]);
	}
	//输出
	return nMaxLen;
}

int main()
{
	int nArr[8] = {1,-1,2,-3,4,-5,6,-7};
	cout<<LIS(nArr,8)<<endl;
	system("pause");
	return 1;
}

代码：输出一个LIS序列

#include <iostream>
#include <assert.h>
using namespace std;

void Print(int* nArr,int* Pre,int nCurPos)
{
	if (nCurPos == -1)
	{
		return;
	}
	Print(nArr,Pre,Pre[nCurPos]);
	cout<<nArr[nCurPos]<<" ";
}

/*
F[i]:表示以nArr[i]为结尾的最长递增子序列的长度
F[i] = Max(F[j]) + 1 && a[i] > a[j] && i > j;
F[i] = 1
*/
int LIS(int nArr[],int nLen)
{
	int nMaxLen = 1;
	int* F = new int[nLen];
	int* Pre = new int[nLen];
	int nMaxPos = -1;
	//递推
	for (int i = 1;i < nLen;i++)
	{
		F[i] = 1;
		Pre[i] = -1;
		for (int j = i - 1;j >= 0;j--)
		{
			if (nArr[i] > nArr[j])
			{
				if (F[i] < F[j] + 1)
				{
					F[i] = F[j] + 1;
					
					Pre[i] = j;
				}
			}
		}
		if (nMaxLen < F[i])
		{
			nMaxLen = F[i];
			nMaxPos = i;
		}
	}
	//输出
	Print(nArr,Pre,nMaxPos);
	cout<<endl;
	return nMaxLen;
}

int main()
{
	int nArr[8] = {1,-1,2,-3,4,-5,6,-7};
	cout<<LIS(nArr,8)<<endl;
	system("pause");
	return 1;
}

思路(2)O(nlogn)的算法

思路：数组nArrIncr中的数据都是不重复的。

代码：

int BinSearch(int nArrIncr[],int nNum,int nStart,int nEnd)
{
	int nMid = -1;
	while(nStart <= nEnd)
	{
		nMid = (nStart + nEnd) >> 1;
		if (nArrIncr[nMid] == nNum)
		{
			return nMid;//返回nNum的位置
		}
		else if (nArrIncr[nMid] > nNum)
		{
			nEnd = nMid - 1;
		}
		else
		{
			nStart = nMid + 1;
		}
	}
	return nStart; //返回第一个大于nNum的位置
}

int LIS(int nArr[],int nLen)
{
	assert(nLen > 0);
	int nEnd = 0;
	int* nArrIncr = new int[nLen];
	nArrIncr[0] = nArr[0];
	int nPos = -1;
	for (int i = 1;i < nLen;i++)
	{
		if (nArr[i] > nArrIncr[nEnd])
		{
			nArrIncr[++nEnd] = nArr[i];
		}
		else
		{
			nPos = BinSearch(nArrIncr,nArr[i],0,nEnd);//寻找第一个大于等于nArr[i]的数
			nArrIncr[nPos] = nArr[i];
		}
	}
	return nEnd + 1;
}

利用STL，给出一个更简洁的代码：

int LIS(int nArr[],int nLen)
{
	assert(nLen > 0);
	int nEnd = 0;
	int* nArrIncr = new int[nLen];
	nArrIncr[0] = nArr[0];
	int nPos = -1;
	for (int i = 1;i < nLen;i++)
	{
		if (nArr[i] > nArrIncr[nEnd])
		{
			nArrIncr[++nEnd] = nArr[i];
		}
		else
		{
			//寻找第一个大于等于nArr[i]的数
			*lower_bound(nArrIncr,nArrIncr + nEnd + 1,nArr[i]) = nArr[i];
		}
	}
	return nEnd + 1;
}

注：

lower_bound作用：在区间[first,last)进行二分查找，返回第一个大于或等于val的元素位置(迭代器)。

(1)如果所有元素都小于val，则返回last的位置，且last的位置是越界的

(2)头文件：#include <algorithm>

输出一个LIS，复杂度为O(n)

代码

#include <iostream>
#include <assert.h>
#include <algorithm>
using namespace std;

void Print(int nArr[],int nCurLen,int nCurPos,int nArrPos[])
{
	if (nCurLen == 0)
	{
		return;
	}
	if (nCurLen == nArrPos[nCurPos])
	{
		Print(nArr,nCurLen - 1,nCurPos - 1,nArrPos);
		cout<<nArr[nCurPos]<<" ";
	}
	else
	{
		Print(nArr,nCurLen,nCurPos - 1,nArrPos);
	}
}

void LIS(int nArr[],int nLen)
{
	assert(nLen > 0);
	int nEnd = 0;
	int* nArrIncr = new int[nLen];
	int* nArrPos = new int[nLen];
	nArrIncr[0] = nArr[0];
	nArrPos[0] = 1; //每一个元素所在LIS的位置
	int nLastNumPos = 0;//LIS最后一个元素的下标
	
	for (int i = 1;i < nLen;i++)
	{
		if (nArr[i] > nArrIncr[nEnd])
		{
			nArrIncr[++nEnd] = nArr[i];
			
			nArrPos[i] = nEnd + 1;//寻找LIS
			nLastNumPos = i;//记录LIS最后一个元素的位置
		}
		else
		{
			//寻找第一个大于等于nArr[i]的数
			int nPos = lower_bound(nArrIncr,nArrIncr + nEnd + 1,nArr[i]) - nArrIncr;
			nArrIncr[nPos] = nArr[i];
			
			nArrPos[i] = nPos + 1;//记录每一个数是在LIS中第几个数
		}
	}
	//输出信息
	cout<<"长度: "<<nEnd + 1<<endl;
	cout<<"LIS: ";
	Print(nArr,nEnd + 1,nLastNumPos,nArrPos);
	cout<<endl;
}

int main()
{
	//int nArr[8] = {1,-1,2,-3,4,-5,6,-7};
	//LIS(nArr,8);

 	int nArr[1] = {-7};
 	LIS(nArr,1);

 	//int nArr[8] = {-7,10,9,2,3,8,8,1};
 	//LIS(nArr,8);
	system("pause");
	return 1;
}