Majority Vote Algorithm
字符串全排序

最长递增子序列

Jimmy posted @ 2011年10月14日 19:35 in Others , 1080 阅读

一.问题描述

设 X = <x_{k1},x_{k2}\ldots,x_{n}>是n个不同的实数序列,L的递增子序列L'= <a_{k1}, a_{k2}\ldots,a_{kn}>,其中x_{k1}<x_{k2}\ldots<x_{km}, 求最大的m值

二.问题求解

2.1 转化为LCS问题求解

设序列A = <a_{k1},a_{k2}\ldots,a_{n}>是序列 X = <x_{k1},x_{k2}\ldots,x_{n}>按递增顺序排好的序列,则A与L的最长公共子序列为L的最长递增子序列。这样把求最长递增子序列问题规约为最长公共子序列问题LCS了。

此解法的时间复杂度为:O(n^2)+O(nlogn)

2.2 使用动态规划求解

maxLength(i)为X中以x_{i}为末元素的最长递增子序列的长度,有如下的递推方程:

maxLength(i) = maxLength(j)+1   x_{i} < x_{j}, k<\neq j < i, maxLength(k) < maxLength(j)

maxLength(i) = 1

即在求以x_{i}为末元素的最长递增子序列长度时,对所有在x_{i}前面的元素x_{j},且x_{j}<x_{i},如果j的值存在,找出maxLength(j)的最大值,则maxLength(i) = maxLength(j)+1,否则maxLength(i) = 1

算法如下:

function lis_length( a )
    n := a.length
    q := new Array(n)
    for k from 0 to n:
        max := 0;
        for j from 0 to k, if a[k] > a[j]:
            if q[j] > max, then set max = q[j].
        q[k] := max + 1;
    max := 0
    for i from 0 to n:
        if q[i] > max, then set max = q[i].
    return max;

程序如下:

/*
**Descrition:	Returns the length of the longest increasing subsequence
**		Note that this is looking for the longest strictly increasing subsequence
**		This can be modified for other situations
**Author:	jia1546@163.com
**Date:		Oct 15, 2011
**Version:	1.0	
*/

#include <stdio.h>
#include <stdlib.h>

int lis(int *a, int n)
{
    int i, j;
    int *best, *prev;
    int max = 0;
    best = (int*)malloc(sizeof(int) * n);
    prev = (int*)malloc(sizeof(int) * n);

    for(i=0; i<n; i++)
    {
	best[i] = 1;
        prev[i] = i;
    }

    for(i=1; i<n; i++)
	for(j=0; j<i; j++)
 	    if(a[i] >= a[j] && best[i] < best[j] + 1)
	    {
		best[i] = best[j] + 1;
 		prev[i] = j;
	    }
    
    for(i=0; i<n; i++)
    	if(max < best[i])
	    max = best[i];

    free(best);
    free(prev);
    
    return max;
}

int main()
{
    int n;
    int *array;
    int i;
    while(scanf("%d",&n) != EOF)
    {
 	array = (int*)malloc(sizeof(int) * n);

	for(i=0; i<n; i++)
	    scanf("%d",array+i);
	printf("# of the lis is: %d\n", lis(array, n));
	
    }
    return 0;
}

时间复杂度: O(n^2)

2.2 改进的动态规划

在上一算法中,在计算maxLength(i)时,需要找出最大的maxLength(j),由于maxLength(j)无序,所以只能顺序查找x_{j} < x{i}的最大值maxLength(j),如果能让maxLength(j)有序,可以使用二分查找的方法降低复杂度到O(nlogn)

数组M[j]存储所有长度为j的子序列中最小末元素的X[k]的下标k

数组P[k]存储以X[k]为末元素的最长递增子序列中X[k]的前一元素的位置

算法如下:

L=0
for i=1,2,...n
    binary search for the largest positive j<=L
     such that X[M[j]] < X[i](or set j=0 if no such j exists)
    P[i] = M[j]
    if  j == L or X[i] < X[M[j+1]]
	M[j+1] = i
	L = max(L, j+1)

程序如下:

#include <vector>
using namespace std;
 
/* Finds longest strictly increasing subsequence. O(n log k) algorithm. */
void find_lis(vector<int> &a, vector<int> &b)
{
	vector<int> p(a.size());
	int u, v;
 
	if (a.empty()) return;
 
	b.push_back(0);
 
	for (size_t i = 1; i < a.size(); i++) 
        {
                // If next element a[i] is greater than last element of current longest subsequence a[b.back()], just push it at back of "b" and continue
		if (a[b.back()] < a[i]) 
                {
			p[i] = b.back();
			b.push_back(i);
			continue;
		}
 
                // Binary search to find the smallest element referenced by b which is just bigger than a[i]
                // Note : Binary search is performed on b (and not a). Size of b is always <=k and hence contributes O(log k) to complexity.    
		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;
		}
 
                // Update b if new value is smaller then previously referenced value 
		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;
}
 
/* Example of usage: */
#include <cstdio>
int main()
{
	int a[] = { 1, 9, 3, 8, 11, 4, 5, 6, 4, 19, 7, 1, 7 };
	vector<int> seq(a, a+sizeof(a)/sizeof(a[0])); // seq : Input Vector
	vector<int> lis;                              // lis : Vector containing indexes of longest subsequence 
        find_lis(seq, lis);
 
        //Printing actual output 
	for (size_t i = 0; i < lis.size(); i++)
		printf("%d ", seq[lis[i]]);
        printf("\n");    
 
	return 0;
}

Ref

http://www.algorithmist.com/index.php/Longest_Increasing_Subsequence

http://en.wikipedia.org/wiki/Longest_increasing_subsequence


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter