c语言最长递增子序列nlogn,最长递增子序列
问题定义：
设有一个长度为N的数组，请确定其中最长的一个单调递增子序列（无需考虑其是否连续排列，在保持原有顺序的基础上寻找）。如示例所示：对于数组A={5,6,7,1,2,8}（注：括号应闭合于整个集合内），则该子序列的最大长度为4。
解法一：最长公共子序列法：
深入分析这个问题时会发现其本质特征是可以通过转化为求解最长公共子序列问题来实现的
递增：A排好序的数组即为单调不降序列，在此情况下任意两个序列都具有相同的最长单调不降子序列。
Subsequence: 因为A数组本身就是原数组, 所以任何A数组中的子序列都保持了顺序一致, 这样就确保了两序列最长公共子序列的顺序保持一致。
最长：显而易见。
具体的解法请参见上一篇博客：
解法二：动态规划法(O(N^2))
动态规划方法的核心便是识别出一个系统的子问题系统。请针对当前的问题，请确定其具体的子问题。
对于长度为N的数组A[N] = {a0, a1, a2, ..., an-1}来说，在计算以aj结尾的最大递增子序列长度时（将其定义为L[j]），我们可以将问题转化为：找出所有满足i < j且a[i] < a[j]的位置i（即i的范围是0到j - 1），并取其中L[i]的最大值加一。这样做的核心思想在于通过动态规划的方式逐步构建每个元素结尾的最长递增子序列长度。为了找到整个数组的最大递增子序列长度，则需要依次对数组中的每一个元素执行上述操作，并记录下所有L[j]中的最大值作为最终结果。
时间复杂度：在每次迭代中都需要将当前元素与其前面所有元素进行比较，则其时间复杂度则达到O(N²)
解法三：动态规划法(O(NlogN))
该方法的时间复杂度仍为O(N²)，与方法一差距不大。深入探讨其原因后发现，在每一步骤中都需要遍历所有前面的位置来计算最长递增子序列的长度。
为了实现这一目标, 我们需要申请一个长度为N的空间,B[N], 并使用变量len来存储当前最长递增子序列的长度
在B数组中每个元素B[i]表示长度为i的最长递增子序列最后一个位置上的数值即该最长递增子序列的最大值。
在有序排列中将d[1]放置于B中，并使B的第一个元素设为2。这表明，在仅有一个数字2存在的情况下（即当仅有一个数字2存在时），长度为1的最长递增子序列（LIS）的最小末尾元素即为2。此时对应的长度参数Len被赋值为1。
接着将d[2]按照一定的顺序放入B中。设定B的第一个元素为1，则表示长度为1的最长递增子序列（LIS）的最小末尾也是1。由于d[0]=2已经被弃用不再参与后续计算，请您容易理解。此时计算得到的结果是Len=1。
接着，在处理第三个元素时发现d_3=5大于当前的第一个元素值B_1=...因此，在位置i+1即位置2处更新元素值到5。这表明长度为2的最佳递增子序列末尾值被确定为5。这时候数组区间从索引范围1到范围包含两个元素即数值分别为1,5此时总长度len等于2
再来，在索引位置4处赋值d=3；由于当前序列中存在两个候选位置（索引位置0和索引位置4），将其放置于位置0显然是不合适的；因为当前序列中的第一个元素已经比目标值小（即B[0]=1 < d=3），所以我们可以确定：长度为2的LIS最小末尾应当是数值3；由此可推断出：当遇到更大的数值时（例如B[4]=5），其插入位置应被优化掉以减少整体序列长度；最终得到的新序列B[0..2]=[B_0,B_2,B_4]=[1,3,5]；此时最长递增子序列的长度更新为Len=3
继续进行下去的话，则会发现d₅的位置已经被确定下来为第六位；具体来说，则会发现这个位置是在前面那个数（即B₂）之后的位置上；因为根据已知条件B₂等于三；而同样地；在这个位置上的数字则是六；从而我们可以得出结论：当我们在计算到第五个元素时；此时数组从第一个元素到第四个元素已经确定为一、三、五和七；那么数组的长度已经达到了四个元素
第6个, d[6] = 4，你看它在3和6之间，于是我们就可以把6替换掉，得到B[3] = 4。B[1..3] = 1, 3, 4， Len继续等于3
第7个, d[7] = 8，它很大，比4大，嗯。于是B[4] = 8。Len变成4了
第8个, d[8] = 9，得到B[5] = 9，嗯。Len继续增大，到5了。
最后一个, d[9] = 7，它在B[3] = 4和B[4] = 8之间，所以我们知道，最新的B[4] =7，B[1..5] = 1, 3, 4, 7, 9，Len = 5。
于是我们知道了LIS的长度为5。
注意这个列表（1,3,4,7,9）并不完整地表示完整的LIS序列。它仅代表对应长度LIS的最小末尾值列表。通过这个列表我们可以依次插入数据元素来进行后续操作。虽然最后一个元素d[9]=7的更新并不显著提升当前序列的效果，在特定情况下如果后续出现数值8和9，则可以将8放置在d[5]的位置，并将9放置在d[6]的位置，这样我们可以确定整个序列的最大递增子序列长度达到了6。
接着会发现一个关键点：B中的数据插入顺序是有规律的，并且其处理方式无需移动数据位置——从而能够采用二分查找方法将单个数据的插入时间优化至O(logN)，因此该算法的整体时间复杂度降至O(N log N)。
#include
using namespace std;
// LIS[j] = max(LIS[i]) + 1
int LIS_DP_N2(int *array, int nLength)
{
int LIS[nLength];
for(int i = 0; i < nLength; i++)
{
LIS[i] = 1;
}
for(int i = 1; i < nLength; i++)
{
int maxLen = 0;
for(int j = 0; j < i; j++)
{
if(array[i] > array[j])
{
if(maxLen < LIS[j])
maxLen = LIS[j];
}
}
LIS[i] = maxLen + 1;
}
int maxLIS = 0;
for(int i = 0; i < nLength; i++)
{
if(maxLIS < LIS[i])
maxLIS = LIS[i];
}
return maxLIS;
}
int BinarySearch(int *array, int value, int nLength)
{
int begin = 0;
int end = nLength - 1;
while(begin <= end)
{
int mid = begin + (end - begin) / 2;
if(array[mid] == value)
return mid;
else if(array[mid] > value)
end = mid - 1;
else
begin = mid + 1;
}
return begin;
}
int LIS_DP_NlogN(int *array, int nLength)
{
int B[nLength];
int nLISLen = 1;
B[0] = array[0];
for(int i = 1; i < nLength; i++)
{
if(array[i] > B[nLISLen - 1])
{
B[nLISLen] = array[i];
nLISLen++;
}
else
{
int pos = BinarySearch(B, array[i], nLISLen);
B[pos] = array[i];
}
}
return nLISLen;
}
int main()
{
int data[6] = {5, 6, 7, 1, 2, 8};
cout<
cout<
return 0;
}