最近在做单调队列,发现了最长上升子序列O(nlogn)的求法也有利用单调队列的思想。
最长递增子序列问题:在一列数中寻找一些数,这些数满足:任意两个数a[i]和a[j],若i<j,必有a[i]<a[j],这样最长的子序列称为最长递增子序列。
设dp[i]表示以i为结尾的最长递增子序列的长度,则状态转移方程为:
dp[i] = max{dp[j]+1}, 1<=j<i,a[j]<a[i].
这样简单的复杂度为O(n^2),其实还有更好的方法。
考虑两个数a[x]和a[y],x<y且a[x]<a[y],且dp[x]=dp[y],当a[t]要选择时,到底取哪一个构成最优的呢?显然选取a[x]更有潜力,因为可能存在a[x]<a[z]<a[y],这样a[t]可以获得更优的值。在这里给我们一个启示,当dp[t]一样时,尽量选择更小的a[x].
按dp[t]=k来分类,只需保留dp[t]=k的所有a[t]中的最小值,设d[k]记录这个值,d[k]=min{a[t],dp[t]=k}。
这时注意到d的两个特点(重要):
1. d[k]在计算过程中单调不升;
2. d数组是有序的,d[1]<d[2]<..d[n]。
利用这两个性质,可以很方便的求解:
1. 设当前已求出的最长上升子序列的长度为len(初始时为1),每次读入一个新元素x:
2. 若x>d[len],则直接加入到d的末尾,且len++;(利用性质2)
否则,在d中二分查找,找到第一个比x小的数d[k],并d[k+1]=x,在这里x<=d[k+1]一定成立(性质1,2)。
例:POJ1631
/**
最长递增子序列O(nlogn)算法:
状态转移方程:f[i] = max{f[i],f[j]+1},1<=j<i,a[j]<a[i].
分析:加入x<y,f[x]>=f[y],则x相对于y更有潜力。
首先根据f[]值分类,记录满足f[t]=k的最小的值a[t],记d[k]=min{a[t]},f[t]=k.
1.发现d[k]在计算过程中单调不上升
2.d[1]<d[2]<...<d[k] (反证) 1 2 3 8 4 7
解法:
1. 设当前最长递增子序列为len,考虑元素a[i];
2. 若d[len]<a[i],则len++,并将d[len]=a[i];
否则,在d[0-len]中二分查找,找到第一个比它小的元素d[k],并d[k+1]=a[i].()
*/
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int N = 41000;
int a[N]; //a[i] 原始数据
int d[N]; //d[i] 长度为i的递增子序列的最小值
int BinSearch(int key, int* d, int low, int high)
{
while(low<=high)
{
int mid = (low+high)>>1;
if(key>d[mid] && key<=d[mid+1])
return mid;
else if(key>d[mid])
low = mid+1;
else
high = mid-1;
}
return 0;
}
int LIS(int* a, int n, int* d)
{
int i,j;
d[1] = a[1];
int len = 1; //递增子序列长度
for(i = 2; i <= n; i++)
{
if(d[len]<a[i])
j = ++len;
else
j = BinSearch(a[i],d,1,len) + 1;
d[j] = a[i];
}
return len;
}
int main()
{
int t;
int p;
scanf("%d",&t);
while(t--)
{
scanf("%d",&p);
for(int i = 1; i <= p; i++)
scanf("%d",&a[i]);
printf("%d\n",LIS(a,p,d));
}
return 0;
}
分享到:
相关推荐
动态规划的经典题目最长上升子序列,而且是经过二分优化的NlogN复杂度算法
此资源有助于帮助初学者较快掌握nlogn算法求动态规划中的经典例题---最长不上升序列(n>100000)
此程序用C程序设计语言编写,用于找出序列当中最长递增子序列。
最长递增子序列 O(Nlogn) 最长的子阵列 矩阵链顺序 最大非邻和 最大乘积子阵列 最大子数组 最大和连续子序列 底部的最小距离 最小硬币兑换 最低成本路径 最小分区 最小大小子阵列总和 表示数字的最小...
##算法最长递增子序列时间复杂度O(nlogn)##接口JAVA swing ##功能更改输入字符串的长度随机生成输入字符串标记输入字符串中最长的递增子序列
LIS 最长上升子序列O(NLOGN) 3 RMQ 区间最值询问3 KMP 模式匹配3 字符串最小表示4 第二章数据结构5 并查集5 HEAP 最小堆5 树状数组6 二维树状数组6 TRIE 字典树6 后缀数组8 LCP 最长公共前缀9 第三章图论11 ...
求一组数的最长上升子序列,时间复杂度为O(nlogn)
最近邻点对O(n^2)和O(nlogn)算法
关于用nlogn的最长子序列算法,在网上摘录的
逆序对(归并排序)O(nlogn).cpp
北大POJ1836-Alignment【O(nlogn)】
北大POJ2533-Longest Ordered Subsequence【O(nlogn)】
北大POJ1804-Brainman【借助Mergesort求逆序数O(nlogn)】
要求算法的时间复杂度不超过O(nlogn)。 最大子段和问题描述:给定由n个整数(可能为负整数)组成的序列a1, a2,…, an, 求该序列形如的子段和的最大值。当所有整数均为负整数时定义其最大子段和为0。依次定义,所求...
5.3 最长上升子序列/最长不下降子序列(LIS) 65 5.3.1 O(n^2) 65 5.3.2 O(nlogn) 66 5.4 Joseph问题 67 5.5 0/1背包问题 68 6 组合数学相关 69 6.1 The Number of the Same BST 69 6.2 排列生成 71 6.3 逆序 72 6.3.1...
5.3 最长上升子序列/最长不下降子序列(LIS) 65 5.3.1 O(n^2) 65 5.3.2 O(nlogn) 66 5.4 Joseph问题 67 5.5 0/1背包问题 68 6 组合数学相关 69 6.1 The Number of the Same BST 69 6.2 排列生成 71 6.3 逆序 72 6.3.1...
快速排序描述:快速排序是对冒泡排序的一种改进,其基本思想是通过一趟排序将待排序记录分隔成独立的两部分,其中一部分记录的...3.递归地(recursively)把小于基准值元素的子数列和大于基准值元素的子数列排序。
算法之NlogN排序算法(csdn)————程序
相对于快速排序有更好的时间效率,以最小堆为例实现