杰 & C++ & Python & DM

最长递增子序列(LIS)解法详述

求数组中最长递增子序列(Longest Increasing Subsequence, LIS

LIS问题是算法中的经典题目,传统的解法是使用动态规划,时间复杂度是O(n^2);改进的方法时间复杂度是O(nlogn)。但是关于改进的算法的介绍尽管网上有很多资源,但是有许多看起来没问题,但是经不起推敲,我看的时候感觉有点看不明白,查阅半天弄懂后再回去看,发现他们的表述有问题,因此总结一下。

这篇总结使用从传统解法逐步改进的演绎方法,并给出一些推理。

如果读者不喜欢这种演绎思考方法,推荐Slyar的方法,他从另一个角度看待这个问题,写得十分简洁,但是没有接触过的话,可能不易理解。

本文仍有许多不足,欢迎指正。



传统的解法是使用动态规划。原理如下:

data[i]表示数组中的第i个元素;

lis[i]表示以元素i结尾的最长递增子序列长度;

那么lis[i] = max(lis[j]) + 1, j {k | data[k] < data[i], k < i}

时间复杂度是O(n^2),它的主要优点是算法简单,可以构造最长递增子序列。

int lis[N];
int LIS_DP(int* data, int n)
{
    memset(lis, 
1, n * sizeof(lis[0]));
    
for(int i=1; i != n; ++i)
    {
        
for(int j=0; j != i; ++j)
        {
            
if(data[i] > data[j] && lis[i] < lis[j]+1)
                lis[i] 
= lis[j] + 1;
        }
    }

    
int max = 0;
    
for(int i=0; i != n; ++i) 
        
if(max < lis[i]) 
            max 
= lis[i];
    
return max;
}


另一种方法稍微有些复杂,它是针对上面方法的一种改进,时间复杂度是O(nlogn)。下面使用渐近的方法来分析获得。

首先我们来分析一下上面算法的不足,在上面的求解中,每个lis[i]求解的时间复杂度是O(n),但这不是必需的

             0  1  2  3  4  5  6  7

data[]:   2  5  6  2  3  4  7  4

lis[]:      1  2  3  1  2  3  4  3

 

例如,当求lis[6]时,是不用和data[3]data[4]比较的,因为已经知道它们所在的最大递增子序列的最后一个元素data[5] < data[6];也就是说,当我们考察第i个元素时,对前面i-1个元素的任何一个递增子序列,如果这个子序列的最后一个元素比data[i]小,那么就可以将data[i]加在这个子序列后面,构成一个新的更长的递增子序列,而不用比较这个子序列前面的元素和data[i]的关系。

由此我们得出第一个启发式方法,当计算lis[i]时,我们只关心每个前i-1元素中递增子序列的最后一个元素的值。

针对第一种方法引入的观点,提出第二个启发式方法,同样求lis[6],对前i-1个元素,获得两个长度为3的递增子序列256234,此时已知data[6] > 6data[6]大于4,所以data[6]可以接在任何一个子序列后面,构成长度为4的新递增序列。这个时候,会发现一个启发方法,data[6]不用和6比较,因为只需data[6]大于4就可以得出一个长度为4的递增序列。

所以得出第二个启发式方法,当计算lis[i]时,对同样长度的子序列,我们只关心它们最后元素的值最小的一个的值。

由此,由一个数组last_min记录上面的值,即当计算lis[i]时,last_min[k]表示前i-1个元素中长度为k的所有递增子序列的最后一个元素的最小值。

max_len表示当前已获得的最长的递增子序列。

当考察data[i]时,如果data[i] > last_min[max_len],那么将data[i]接在这个序列后面,便构成一个新的长度为max_len+1的序列,该序列的最后一个元素是data[i];否则,找到一个最大的j,使last_min[j]<data[i](由于查找方式,也说明data[i]<=last_min[j+1]),那么把data[i]接在这个序列后面,便构成一个长度为j+1的新序列,更新last_min[j+1]


int lis[N];                // lis[i]表示以元素i结尾的最长递增子序列长度
int last_min[N];        // last_min[i]表示长度为i的所有递增子序列的
                        
// 最后一个元素的最小值
int max_len;
int LIS_DP(int* data, int n)
{
    memset(lis, 
1, n * sizeof(lis[0]));
    last_min[
1= data[0];
    max_len 
= 1;
    
for(int i=1; i != n; ++i)
    {
        
// 如果data[i]比最长递增序列的最后一个元素大,
        
// 那么直接加在它后面便可
        if (data[i] > last_min[max_len])
        {
            
++max_len;
            last_min[max_len] 
= data[i];
            lis[i] 
= max_len;
        }
        
else
        {
            
// 否则查找历史最长递增序列
            for(int j=max_len-1; j != 0--j)
            {
                
if (data[i] > last_min[j])  // 也就是说,data[i] <= last_min[j+1]
                {
                    lis[i] 
= j + 1;
                    last_min[j
+1= data[i]; //更新
                    break;
                }
            }
        }
    }
    
return max_len;
}


如上所示,虽然已经进行了很大的优化,但是当前的时间复杂度仍是O(n^2),当然基本可以确定的是,现在的算法比原来的效率提高了很多。

下面我们分析一下last_min数组的性质,

由定义last_min[i]表示长度为i的序列A的最后一个元素的值,last_min[i-1]表示长度为i-1的序列B的最后一个元素的值,那么last_min[i-1]<last[i];否则序列A的前i-1个元素构成的序列便可替代序列B。所以last_min是有序的。

因此在上面的查找中可以使用二分查找,效率为O(logn),使得总的复杂度为O(nlogn)


 

// 返回arr中等于或第一个大于val的位置
int BinarySearch(int* arr, int left, int right, int val)
{
    
int mid = 0;
    
int l = left;
    
int r = right;

    
while (l <= r)
    {
        mid 
= (l + r) >> 1;
        
if (arr[mid] > val) r = mid - 1;
        
else if (arr[mid] < val) l = mid + 1;
        
else return mid;
    }
    
return l;
}

int last_min[N];        // last_min[i]表示长度为i的所有递增子序列的
                        
// 最后一个元素的最小值
int max_len;    
int LIS_DP(int* data, int n)
{
    last_min[
1= data[0];
    max_len 
= 1;
    
for(int i=1; i != n; ++i)
    {
        
// 如果data[i]比最长递增序列的最后一个元素大,
        
// 那么直接加在它后面便可
        if (data[i] > last_min[max_len])
        {
            
++max_len;
            last_min[max_len] 
= data[i];
        }
        
else
        {
            
// 否则查找历史最长递增序列
            int j = BinarySearch(last_min, 1, max_len, data[i]);
            last_min[j] 
= data[i];
        }
    }
    
return max_len;
}

在程序二中,lis数组完全没有作用,所以在程序三中没有使用。

与程序一相比,程序三在效率上有明显的提升,但是不能根据last_min构造出最长递增子序列。

 

参考文献

   编程之美—微软技术面试心得.2.16节


 


posted on 2011-06-09 23:44 jaysoon 阅读(2989) 评论(0)  编辑 收藏 引用 所属分类: ACM/ICPC


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


<2024年11月>
272829303112
3456789
10111213141516
17181920212223
24252627282930
1234567

导航

统计

常用链接

留言簿

随笔分类

随笔档案

文章分类

文章档案

收藏夹

C++

搜索

最新评论

阅读排行榜

评论排行榜