[cpp]
for(i=0, j=n-1; i
return (i,j);
else if(a[i]+a[j]
else
--j;
return (-1,-1);
8、数组中最长递增子序列 www.2cto.com
如在序列1,-1,2,-3,4,-5,6,-7中，最长递增序列为1,2,4,6。
问题满足无后效性，可以用动态规划来解。
目标数组a[]的前i个元素中，最长递增子序列长度为LIS[i]。
则：LIS[i+1]=max{1,LIS[k]+1},for any k<=i,a[i+1]>a[k]
动态规划法：
int LIS(int a[], int length)
{
int LIS[]=new int[length];
for(int i=0;i
LIS[i]=1; //初始化默认长度
for(int j=0;j
LIS[i]=LIS[j]+1;
}
return Max(LIS); //取LIS的最大值
}
这种方法时间复杂度为O(N^2+N)=O(N^2)
作者：luxiaoxun