int LIS(int[] array)
{
// 记录数组中的递增序列信息
int[] MaxV = new int[array.Length + 1];
MaxV[1] = array[0]; // 数组中的第一值,边界值
MaxV[0] = Min(array) - 1; // 数组中最小值,边界值
int[] LIS = new int[array.Length];
// 初始化最长递增序列的信息
for(int i = 0; i < LIS.Length; i++)
{
LIS[i] = 1;
}
int nMaxLIS = 1; // 数组最长递增子序列的长度
for(int i = 1; i < array.Length; i++)
{
// 遍历历史最长递增序列信息
int j;
for(j = nMaxLIS; j >= 0; j--)
{
if(array[i] > MaxV[j])
{
LIS[i] = j + 1;
break;
}
}
// 如果当前最长序列大于最长递增序列长度,更新最长信息
if(LIS[i] > nMaxLIS)
{
nMaxLIS = LIS[i];
MaxV[LIS[i]] = array[i];
}
else if (MaxV[j] < array[i] && array[i] < MaxV[j + 1])
{
MaxV[j + 1] = array[i];
}
}
return nMaxLIS;
}