Longest Increasing Subsequence

题目

uva 481: What Goes Up 

http://uva.onlinejudge.org/external/106/10684.html

这个问题是这样:给定一个数组a[0...n],求它的单调严格递增子序列的最大长度,并给出一个示例解。子序列是从最初序列通过去除0个或多个元素但不破坏余下元素的相对位置而形成的新序列。严格单调递增是这个序列中每个元素都小于后一个元素,不能等于,也不能大于。

例如:-7 10 9 2 3 8 8 1 的解是4,其中一个长度为4的LIS是:

-7 2 3 8

例如:0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15 的解是6,其中一个长度为6的LIS是:

0, 2, 6, 9, 11, 15

这就是一个很普通的求 LIS(Longest Increasing Subsequence)的问题。我本来LIS以为和LCS很像,但是实际写一下发现,这个东西挺难的,花了我整整一下午的时间才写好。

解法一

首先,基本思路是用动态规划,自下而上的把解构造出来。

要使用动态规划,就得有最优子结构。下面来分析一下。

把原来的问题稍微加点限制。设LIS(i) : 以a[i]为右端点的单调严格递增子序列 (加了以a[i]为右端点这个限制)

那么显然有LIS(0) = a[0];

LIS(i) = max { LIS(j)  : a[j]<a[i] && 0<=j<i } .append( a[i] );

所以在O(n^2) 的时间内,就能求出最大长度。

另外,如果我们直接存储n个LIS,那么空间消耗是O(n^2)的。所以实际计算中可以采用下面这样的方法:

先用一个数组m,其中m[i] =  LIS(i)的长度。所以m最终的长度和输入数组a的长度一样。

另外一个数组indexes

indexes[i]: 以a[i]为结尾的lis的a[i]的上一个的(index+1)。0,没了 。

这个有点像链表。我用0来标志结束,所以不得不在存index的时候都先加1,再存入。最终通过遍历链表的方式遍历这个数组,就可以得到子序列。 代码如下:

 //return the indexes of the origin array
 template <typename T>
 std::vector<size_t> lis(const std::vector<T>& a){
    if(a.empty())
      throw std::runtime_error("err");
    if(a.size()==1)
      return std::vector<size_t>(1,0);
    std::vector<size_t> m(a.size(),1);
    //indexes[i]: 以a[i]为结尾的lis的a[i]的上一个的index。0,没了
    std::vector<size_t> indexes(a.size(),0);
    size_t top(0);
    for(size_t i=1;i!=a.size();++i){
      for(size_t j=0;j<i;++j){
        if(a[j]<a[i] && m[j]+1 > m[i]){
          m[i]=m[j]+1;
          indexes[i]=j+1;
        }
        if(m[i]>m[top]) top=i;
      }
    }
    std::vector<size_t> ret(m[top],0);
    size_t len=ret.size();
    for(size_t i=ret.size();i!=0;){
      i--;
      ret[i]=top;
      size_t t=indexes[top];
      if(i && !t) throw std::runtime_error("err");
      top=t-1;
    }
    return ret;
  }

但是很悲剧,代码提交上去之后,超出了时间限制。因为这个问题存在O(nlgn)甚至O(nlglgn)的解法。下面细述O(nlgn)的是怎么来的。

解法二

首先,在每次求下面这个max的时候,

OPT(i) = max{a[j]<a[i] ? OPT[j]+1:1} , j=0...i-1;

如果a[j]是有序的,那么这个max操作将会只花费O(lgn)的时间。怎么办呢?

如果我们把LIS(0), LIS(1) ... LIS(n) 按照长度,从小到大排序。那么会发现,长度越长的,它最右端的元素也应该较大。

等等,什么是较大? 唔...  如果排序后,我们发现LIS(i) 和 LIS(j)的长度一样,但是a[i] 比a[j]小,那么我们就把LIS(j)从计算中丢弃掉。因为 能拼在LIS(j)后面的序列肯定也能拼在LIS(i)后面。

删掉那些长度重复的元素后,得到的新数组记作M 。下面来看一个例子:

假设输入为

A[] ={0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15},

令M[i] = 长度为i的所有LCS中最右端的元素最小的一个。

那么:

A[0] = 0,
M[0] = {0} ,


A[1] = 8,
M[0] = {0},

M[1] = {0, 8}

A[2] = 4,
M[0]={0}

M[1]={0, 4}

A[3] = 12
M[0]={0}
M[1]={0, 4}

M[2]={0, 4, 12}

A[4] = 2
M[0]={0}

M[1]={0, 2}

M[2]={0, 4, 12}


A[5] = 10,
M[0]={0}
M[1]={0, 2}

M[2]={0, 2, 10}

A[6] = 6,
M[0]={0}
M[1]={0, 2}

M[2]={0, 2, 6}

A[7] = 14,
M[0]={0}
M[1]={0, 2}
M[2]={0, 2, 6}

M[3]={0, 2, 6, 14}

A[8] = 1,
M[0]={0}

M[1]={0, 1}

M[2]={0, 2, 6}
M[3]={0, 2, 6, 14}


A[9] = 9,
M[0]={0}
M[1]={0, 1}
M[2]={0, 2, 6}

M[3]={0, 2, 6, 9}

A[10] = 5,
M[0]={0}
M[1]={0, 1}

M[2]={0, 1, 5}

M[3]={0, 2, 6, 9}


A[11] = 13,
M[0]={0}
M[1]={0, 1}
M[2]={0, 1, 5}
M[3]={0, 2, 6, 9}

M[4]={0, 2, 6, 9, 13}

A[12] = 3,
M[0]={0}
M[1]={0, 1}

M[2]={0, 1, 3}

M[3]={0, 2, 6, 9}
M[4]={0, 2, 6, 9, 13}


A[13] = 11,
M[0]={0}
M[1]={0, 1}
M[2]={0, 1, 3}
M[3]={0, 2, 6, 9}

M[4]={0, 2, 6, 9, 11}

A[14] = 7,
M[0]={0}
M[1]={0, 1}
M[2]={0, 1, 3}

M[3]={0, 1, 3, 7}

M[4]={0, 2, 6, 9, 11}


A[15] = 15,
M[0]={0}
M[1]={0, 1}
M[2]={0, 1, 3}
M[3]={0, 1, 3, 7}
M[4]={0, 2, 6, 9, 11}

M[5]={0, 2, 6, 9, 11, 15}  < LIS List

可以看出,M的最右端元素是严格单调递增的。如果把它们拿出来组成一个数组,那么每次是拿a[i]在这个数组中做二分查找,替换掉比a[i]大的当中最小的一个。如果没有比a[i]大的,那么恭喜,最大长度加1。 
所以实际写程序的时候,我不需要把M[i] 对应的LCS全部保存下来,我只需要保存它最右端的元素即可。

//a[M[i]]是长度为i+1的LIS的最大的元素 
std::vector<sizet> M(1, 0);
然后和之前一样,再用一个数组来保存index 
//P[i]: 以a[i]为结尾的lis的a[i]的上一个的index。0,没了 
std::vector<size
t> P(len, 0); 

最终全部代码如下:

/*!
 * 一个functor,在二分查找中使用
 */
template <typename Iterator> class liscomp {  
 private:
  const Iterator a;

 public:
  liscomp(const Iterator& a1) : a(a1) {}
  //test if a[i]<a[j]
  bool operator()(size_t i, size_t j) const { return *(a + i) < *(a + j); }
};

/**
 * 在[begin,end)中寻找长度最大的严格单调递增子序列,返回它们的下标
 * \return 在原数组中的下标,即相对于begin的偏移
 */
template <typename Iterator>  
std::vector<size_t> lis2(Iterator begin, Iterator end) {  
  if (end <= begin) throw std::runtime_error("Range Error");
  const size_t len = end - begin;
  //假设输入的数组为a[0...len-1]
  //如果a长度为1,则它的LCS就是a[0]
  if (len == 1) return std::vector<size_t>(1, 0);
  //a[M[i]]是长度为i+1的LIS的最大的元素
  //所以a[M[0]]是长度为1的LIS的最大元素,所以初始应为a[0]
  //所以M[0]=0
  std::vector<size_t> M(1, 0);
  //P[i] : LCS中a[i]的上一个的index(从1开始,即a[0]对应1)。
  //若P[i]==0,则没有上一个了,a[i]就是这个LCS的开头元素
  //初始化一个长度为len的vector,每个元素都是0
  std::vector<size_t> P(len, 0);
  //从a的第二个元素开始循环,前面已经检查过len>1
  for (size_t i = 1; i != len; ++i) {
    //look for min(j) in M 满足a[M[j]]>=a[i]
    //case 1. j不存在,也就是说找不到和a[i]相等或更大的。
    //case 2. j==0,于是a[i]比a[0..i-1]都小。
    //case 3. j is in [1...M.size)
    //下面的iter-M.begin() == j
    std::vector<size_t>::iterator iter =
        std::lower_bound(M.begin(), M.end(), i, liscomp<Iterator>(begin));
    if (iter == M.end()) {  //case 1:
      //因为a[i]比它们都大,所以我们可以得到一个更长的LCS
      //这个新LCS的倒数第二个元素也就是a[M.back()]
      //加1是因为P里面存的是从1开始的序号
      P[i] = M.back() + 1;
      M.push_back(i);
    } else if (iter == M.begin()) {  //case 2:
      //a[i]无法和之前任何一个LCS拼在一起
      //它只能自己成为一个长度为1的LCS
      P[i] = 0;
      //但是它比之前那个长度为1的LCS要小,所以替换掉它
      M[0] = i;
    } else {  //case 3:
      P[i] = *(iter - 1) + 1;
      //更新M中现有的值
      *iter = i;
    }
  }

  //backtracking,构造出lis的index序列
  std::vector<size_t> ret(M.size(), 0);
  size_t top = M.back();
  //从ret的最后面,逆着往前写
  for (size_t i = ret.size(); i;) {
    i--;
    ret[i] = top;
    size_t t = P[top];
    if (i && !t) throw std::runtime_error("err");  //should never throw
    top = t - 1;
  }
  return ret;
}

此博客中的热门博文

少写代码,多读别人写的代码

在windows下使用llvm+clang

tensorflow distributed runtime初窥