欢迎来到入门教程网!

C语言

当前位置:主页 > 软件编程 > C语言 >

求数组中最长递增子序列的解决方法

来源:本站原创|时间:2020-01-10|栏目:C语言|点击:

存储扩展算法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),使得array[b[0]]<array[b[1]]<…<array[b[m]]。

解法一
根据无后效性的定义我们知道,将各阶段按照一定的次序排列好之后,对于某个给定的阶段状态来说,它以前各阶段的状态无法直接影响它未来的决策,而只能间接地通过当前的这个状态来影响。换句话说,每个状态都是历史的一个完整总结。
同样的,仍以序列1,-1,2,-3,4,-5,6,-7为例,我们在找到4之后,并不关心4之前的两个值具体是怎样,因为它对找到6没有直接影响。因此,这个问题满足无后效性,可以通过使用动态规划来解决。
可以通过数字的规律来分析目标串:1,-1,2,-3,4,-5,6,-7。
使用i来表示当前遍历的位置
当i=1时,显然,最长的递增序列为(1),序列长度为1.
当i=2是,由于-1<1。因此,必须丢弃第一个值后重新建立串。当前的递增序列为(-1),长度为1。
当i=3时,由于2>1,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+1个元素可以接在LIS[k]长的子序列后面构成一个更长的子序列。于此同时array[i+1]本身至少可以构成一个长度为1的子序列。
根据上面的分析,就可以得到代码清单:
C++代码:

复制代码 代码如下:

int Max(int *a, int n)
{
     int max = a[0];
     for(int i = 1; i < n; i++)
  if(max < a[i])
max = a[i];
     return max;
}
int LIS(vector<int> &array)
{
     int *a = new int[array.size()];
     for(int i = 0; i < array.size(); i++)
     {
 a[i] = 1;//初始化默认的长度
  for(int j = 0; j < i; j++)    //前面最长的序列
  {
     if(array [i] > array [j] && a[j] + 1 > a[i])   //当前数字比第j个大,且标记数组需要更新
{
     a[i] = a[j] + 1;
}
  }
     }
     return Max(a, array.size());
}

这种方法的时间复杂度为O(N2 + N) = O(N2)

解法二
在前面的分析中,当考察第i+1个元素的时候,我们是不考虑前面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)。
那么,只要4>2,就可以把4直接增加到前面的子序列中形成一个新的递增子序列。
因此,我们希望找到前i个元素中的一个递增子序列,使得这个递增子序列的最大的元素比array[i+1]小,且长度尽量地长。这样将array[i+1]加在该递增子序列后,便可以找到以array[i+1]为最大元素的最长递增子序列。
仍然假设在数组的前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]<b[l],则显然应该将b[l]的只改变为a[i],当b[l]≤a[i]≤b[k]时,注意到数组b是有序的,可以用二分搜索算法找到下标j,使得b[j-1]≤a[i]≤b[j]。此时,b[1;j-1]和b[j+1;k]的值不变,b[j]的值改变为a[i]。
复制代码 代码如下:

/* Finds longest strictly increasing subsequence. O(n log k) algorithm. */
template<typename T> vector<int> find_lis(vector<T> &a)
{
  vector<int> 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;
}

上一篇:c++实现strcat字符串连接库函数的方法详解

栏    目:C语言

下一篇:递归形式与非递归形式的斐波那契数列的用法分析

本文标题:求数组中最长递增子序列的解决方法

本文地址:https://www.xiuzhanwang.com/a1/Cyuyan/4425.html

网页制作CMS教程网络编程软件编程脚本语言数据库服务器

如果侵犯了您的权利,请与我们联系,我们将在24小时内进行处理、任何非本站因素导致的法律后果,本站均不负任何责任。

联系QQ:835971066 | 邮箱:835971066#qq.com(#换成@)

Copyright © 2002-2020 脚本教程网 版权所有