存储器扩展算法n2编程c编写时间复杂度尽可能低的程序，求出一维数组(n个要素)中的最长增加部分序列的长度。
例如，在序列1、-1、2、-3、4、-5、6和-7中，最长增加子序列是1、2、4、6或-1、2、4和6 . (编程之美P198-202 )
分析和解法根据主题的要求，求出一维排列中的最长增加部分序列，即查找标签的序列b[0]、b[1]、…、b[m](0=b[0]b[1]…b[m]n )，进行阵列[ b ]
根据解法无后验效应的定义，将各阶段按一定顺序排列后，发现对于给定阶段的状态而言，之前各阶段的状态不能直接影响将来的决策，只能间接影响现在的这种状态。 也就是说，各种状态是历史的完整总结。
同样，以序列1、- 1、2、- 3、4、- 5、6、-7为例，找到4后，也不直接影响找到6，所以不在乎4以前的两个值具体是什么样的。 因此，这个问题可以通过满足无后验效应、使用动态规划来解决。
可以根据数字规律分析目标序列： 1、- 1、2、- 3、4、- 5、6、-7。
使用I表示当前导线测量的位置
i=1时，明显最长的增加序列为(1)，序列长度为1。
因为i=2是-11。 因此，必须放弃第一个值，然后重新构建字符串。 的当前增量序列为(-1 )，长度为1。
i=3时，由于21、2-1。 因此，最长的增加序列为(1，2 )、)-1，2 )，长度为2。 这里，2的前面是1还是-1对之后的递增序列的求出没有直接影响。 (但是，否则可能会有影响)
这样类推的结果，我们得出了以下结论。
假设目标数组array[]的前I个元素中，最长的增量子序列的长度为LIS[i]。 那么，
LIS[i 1]=max{1，LIS[k] 1}，array[i 1]array[k]，for any k=i
也就是说，如果array[i 1]大于array[k]，则第I个元素可以构成紧接在LIS[k]的长子序列之后的更长的子序列。 同时，array[i 1]自身可以构成至少一个长度的子序列。
根据上述分析，可以得到代码清单。
c代码：
intmax(int*a，int n ) ) )。
{
int max=a[0]；
for(intI=1； i n； I )
if(maxa[I] ) ) ) ) )。
max=a[i]；
返回最大值；
}
intl is (向量阵列) )。
{
int*a=newint[Array.size(]；
for(intI=0； i array.size (； I )
{
a[i]=1； //初始化默认长度
for(intj=0； j i； j(//前面最长的序列
{
阵列[ I ]阵列[ j ] a [ j ] 1a [ I ] (if ) /当前数字大于第j个，需要更新标记数组
{
a[i]=a[j] 1；
}
}
}
returnmax(a，array.size ) )；
}
该方法的时间复杂度为o(n2n ) o(n2n )
解法二在上述分析中，考察第I个元素时，我们不考虑上述I个元素的分布情况。 现在让我们从另一个角度分析一下。 也就是说，在考察第i 1个元素时，要考虑前面I个元素的情况。
对于前面的I个元素中的任何增加子序列，如果此子序列的最大元素小于array[i 1]，那么可以在此子序列之后添加array[i 1]以组成新的增加子序列。
例如i=4时，目标序列为1、- 1、2、- 3、4、- 5、6、-7最长增加序列为- 1、2、- 1、2。
在中，仅42，可以将4直接添加到前面的子序列以形成新的增加子序列。
因此，希望找到前I个元素中的一个增量子序列，使该增量子序列的最大元素小于array[i 1]，长度尽可能长。 因此，通过将数组[I1]添加到递增子序列中，可以找到以数组[I1]为最大元素的最长递增子序列。
在数组的前I个要素中，将以array[i]为最大要素的最长增加部分序列的长度设为LIS[i]。
同时，假设：
长度为1的增加子序列的最大元素的最小值为MaxV[1]；
长度为2的增加子序列的最大元素的最小值为MaxV[2]；
.
长度为LIS[i]的增加子串的最大要素的最小值为MaxV[LIS[i]]；
本循环不变式p为： p
：k是序列a[0:i]的最长递增子序列的长度，0≤i＜n。容易看出，在由i-1到i的循环中，a[i]的值起关键作用。如果a[i]能扩展序列a[0;i-1]的最长递增子序列的长度，则k=k+1，否则k不变。设a[0;i-1]中长度为k的最长递增子序列的结尾元素是a[j](0≤j≤i-1)，则当a[i]≥a[j]时可以扩展，否则不能扩展。如果序列a[0;i-1]中有多个长度为k的最长递增子序列，那么需要存储哪些信息？容易看出，只要存储序列a[0;i-1]中所有长度为k的递增子序列中结尾元素的最小值b[k]。因此，需要将循环不变式P增强为：
P：0≤i＜n;k是序列a[0;i]的最长递增子序列的长度；
b[k]是序列a[0;i]中所有长度为k的递增子序列中最小结尾元素值。
相应地，归纳假设也增强为：已知计算序列a[0;i-1](i＜n)的最长递增子序列的长度k以及序列a[0;i]中所有长度为k的递增子序列中的最小结尾元素值b[k]的正确算法。
增强归纳假设后，在由i-1到i的循环中，当a[i]≥b[k]时，k=k+1，b[k]=a[i],否则k值不变。注意到当a[i]≥b[k]时，k值增加，b[k]的值为a[i]。那么，当a[i]＜b[k]时，b[l;k]的值应该如何改变？如果a[i]
/* Finds longest strictly increasing subsequence. O(n log k) algorithm. */
template vector find_lis(vector &a)
{
vector b, p(a.size());//b是存储递增序列长度为k的最后元素下标
//比如b[1]是存储递增子序列最大元素的最小值的下标
//b是存储最长子序列的下标
int u, v;
if (a.size() < 1)
return b;
b.push_back(0);
for (int i = 1; i < (int)a.size(); i++)
{
if (a[b.back()] < a[i])
{
p[i] = b.back();
b.push_back(i);
continue;
}
for (u = 0, v = b.size()-1; u < v;) //二分搜索
{
int c = (u + v) / 2;
if (a[b[c]] < a[i])
u=c+1;
else v=c;
}
if (a[i] < a[b[u]])
{
if (u > 0)
p[i] = b[u-1];
b[u] = i;
}
}
for (u = b.size(), v = b.back(); u--; v = p[v])
b[u] = v;
return b;
}