动态规划——最长递增子序列
最长递归子序列
成都创新互联公司自2013年创立以来,是专业互联网技术服务公司,拥有项目成都网站设计、成都网站建设网站策划,项目实施与项目整合能力。我们以让每一个梦想脱颖而出为使命,1280元北镇做网站,已为上家服务,为北镇各地企业和个人服务,联系电话:18980820575
设L= 1.时间复杂度为O(n2),空间复杂度O(n)的算法 2.时间复杂度O(n*log n),空间复杂度O(n)的算法//O(n2)
int LIS1(const int arr[], const int size)
{
vector
int BinSearch(int key, int* d, int low, int high)
{
while(low<=high)
{
int mid = (low+high)>>1;
if(key>d[mid] && key<=d[mid+1])
return mid;
else if(key>d[mid])
low = mid+1;
else
high = mid-1;
}
return 0;
}
int LIS(int* a, int n, int* d)
{
int i,j;
d[1] = a[1];
int len = 1; //递增子序列长度
for(i = 2; i <= n; i++)
{
if(d[len]
网站名称:动态规划——最长递增子序列
文章路径:http://scyanting.com/article/gsegec.html