问题描述
对于一串数 A={a1a2a3...an}, 它的子序列为 S={s1s2s3...sn}, 满足{s1<s2<s3<...<sm}. 求 A 的最长子序列的长度.
动态规划法
算法描述:
设数串的长度为 n,L[i]为以第 i 个数为末尾的最长上升子序列的长度, a[i]为数串的第 i 个数.
L[i]的计算方法为: 从前 i-1 个数中找出满足 a[j]<a[i](1<=j<i)条件的最大的 L[j],L[i]等于 L[j]+1.
动态规划表达式:
代码实现:
- int LIS(int a[], int n)
- {
- int len[MAXSIZE];
- int i, j;
- int maxlen = 0;
- // 计算以第 i 个数为结尾的最长上升子序列的长度
- for (i = 1; i <= n; i++)
- {
- len[i] = 0;
- // 从前 i-1 个数中找出满足 a[j]<a[i](1<=j<i)条件的最大的 L[j]
- for (j = i-1; j>= 1; j--)
- {
- if (a[j] <a[i] && len[j]> len[i])
- {
- len[i] = len[j];
- }
- }
- len[i]++;
- if (len[i]> maxlen)
- {
- maxlen = len[i];
- }
- }
- return maxlen;
- }
上述算法的时间复杂度为 O(n2).
改进算法:
在从前 i-1 个数中找出满足 a[j]<a[i](1<=j<i)条件的最大的 L[j]的时间复杂度为 O(n), 这里采用二分查找的方法对它进行优化, 使其复杂度降为 O(nlogn).
增设一个 m[]数组, m[x]存放长度为 x 的最长上升子序列的最小末尾数. 例: m[3] = 17 表示长度为 3 的最长上升子序列的最小末尾数为 17.
由于子序列是上升的, 所以 m 数组中的元素有一个性质, 当 x<y 时, m[x]<m[y], 利用这个性质来使用二分查找.
设 m 数组所存储的最长上升子序列的长度为 k, 当前计算的数为第 i 个
如果 a[i]>m[k], 则 m[++k]=a[i];
否则在 m[1~k]内二分查找小于 (等于)a[i] 的最大值的位置 p,m[p]=a[i].
代码实现:
- int BSearch(int a[], int n, int t)
- {
- int low = 1;
- int high = n;
- while (low <= high)
- {
- int mid = (low + high) / 2;
- if (t == a[mid])
- {
- return mid;
- }
- else if (t> a[mid])
- {
- low = mid + 1;
- }
- else
- {
- high = mid - 1;
- }
- }
- return low;
- }
- int LIS_BSearch(int a[], int m[], int n)
- {
- int maxlen = 1; // 最长上升子序列的长度
- m[maxlen] = a[1];
- int i;
- for (i = 2; i <= n; i++)
- {
- if (a[i]> m[maxlen])
- {
- m[++maxlen] = a[i];
- }
- else
- {
- // 返回小于 a[i]的最大值的位置 p
- int p = BSearch(m, maxlen, a[i]);
- m[p] = a[i];
- }
- }
- return maxlen;
- }
改进后的算法时间复杂度为 O(nlogn).
最长上升子序列(Longest increasing subsequence)
来源: http://www.bubuko.com/infodetail-2923279.html