`
BlogDown
  • 浏览: 212037 次
  • 性别: Icon_minigender_1
  • 来自: 上海
文章分类
社区版块
存档分类
最新评论

动态规划——最长递增子序列 收藏

 
阅读更多


一,问题描述

设L=<a1,a2,…,an>是n个不同的实数的序列,L的递增子序列是这样一个子序列Lin=<aK1,ak2,…,akm>,其中k1<k2<…<km且aK1<ak2<…<akm。求最大的m值。

二,问题求解

方法一:转化为LCS

根据求LCS方法,将序列L按递增顺序排列,然后存放在数组M中,于是求序列L的最长递增子序列就转化成求序列L和M的LCS。

方法二:动态规划直接求解(一)

以坐标i结尾的序列的最长递增子序列和其[0,i-1]“前缀”的最长递增子序列有关,设C[i]保存“以i结尾的最长递增子序列”的长度,若i=0,则 C[i]=1。否则C[i]的值和其[0,i-1]前缀的最长递增子序列长度有关,用j遍历[0,i-1]得到其最长递增子序列为C[j],对每一个C[j],如果L[j]<L[i]并且C[j]+1>C[i](初始化为0),则C[i]的值变为C[j]+1。即:

LIS[i]=max{1,LIS[j]+1},

其中array[i]>array[j],且j=[0,i-1]。

实现如下:


public void lis(float[] L)


{

int n = L.length;

int[] f = new int[n];//用于存放f(i)值;

f[0]=1;//以第a1为末元素的最长递增子序列长度为1;

for(int i = 1;i<n;i++)//循环n-1次

{

f[i]=1;//f[i]的最小值为1;

for(int j=0;j<i;j++)//循环i 次

{

if(L[j]<L[i]&&f[j]>f[i]-1)

f[i]=f[j]+1;//更新f[i]的值。

}

}

System.out.println(f[n-1]);

}

其中最长递增子序列的值为max(f[n-1])。

方法三:动态规划(二)


在前面的分析中,当考察第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;}http://blog.programfan.com/article.asp?id=13086 http://blog.csdn.net/ztj111/archive/2008/07/31/2748152.aspx

分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics