问题描述:给出一个序列,找出其最长不降子充
例如:4 1 3 5 6 2 7结果为:1 3 5 6
题解:
数组ID[n] = {4 1 3 5 6 2 7}.
数组F[n],设j指向ID,i指向F,F[i]表示在长度为j的序列中,最长不降子序长度为i的子序列的最后一个元素的最小值。所以递推公式为:
0<=i<=len(len:为已求出的最长不降子序的长度)
如果ID[j] <= F[i] (即:长度为i的不降子序的最后一个元素有更小的值ID[j],
则更新F[i])则F[i] = ID[j]
如果i == len 并且 ID[j] > F[i ] (即:ID[j] 可以叠加到已求出的最长子序列上,成为len = len+1长度的不降子序上)。则F[i +1] = ID[j]
则最后我们的答案就是len
这样很明显我们的程序有两个for循环,分别是i,j(0<=j<=n,0<=i<=len)
这样一个个查找的时间为n*n
由于F[i]表示在长度为j的序列中,最长不降子序长度为i的子序列的最后一个元素的最小值,所以F为递增,可以用二分查找法找出将要刷新的F单元.
二分查找的时间为logn
所以总时间为n*logn
zju一道典型题
http://acm.zju.edu.cn/show_problem.php?pid=1986
输入数据量比较大,一定要用C的输入输出才可以AC
#include <iostream>
#include <stdio.h>
using namespace std;
int ID[40000],F[40000];
int main()
{
int Case,N;
//cin>>Case;
scanf("%d",&Case);
for(int i=0; i<Case; i++){
//cin>>N;
scanf("%d",&N);
int len = 0;
for(int j=0; j<N; j++){
//cin>>ID[j];
scanf("%d",&ID[j]);
//二分查找
int left=0,right=len-1;
int mid = 0;
while(left<=right){
mid = (left + right)/2;
if(ID[j] < F[mid])
right = mid-1;
else
left = mid+1;
}
if(left != len)
F[left] = ID[j];
else
F[len++]=ID[j];
}
//cout<<len<<endl;
printf("%d\n",len);
}
return 0;
}
分享到:
相关推荐
此资源有助于帮助初学者较快掌握nlogn算法求动态规划中的经典例题---最长不上升序列(n>100000)
动态规划的经典题目最长上升子序列,而且是经过二分优化的NlogN复杂度算法
此程序用C程序设计语言编写,用于找出序列当中最长递增子序列。
最长递增子序列 O(Nlogn) 最长的子阵列 矩阵链顺序 最大非邻和 最大乘积子阵列 最大子数组 最大和连续子序列 底部的最小距离 最小硬币兑换 最低成本路径 最小分区 最小大小子阵列总和 表示数字的最小...
算法之NlogN排序算法(csdn)————程序
关于用nlogn的最长子序列算法,在网上摘录的
要求算法的时间复杂度不超过O(nlogn)。 最大子段和问题描述:给定由n个整数(可能为负整数)组成的序列a1, a2,…, an, 求该序列形如的子段和的最大值。当所有整数均为负整数时定义其最大子段和为0。依次定义,所求...
##算法最长递增子序列时间复杂度O(nlogn)##接口JAVA swing ##功能更改输入字符串的长度随机生成输入字符串标记输入字符串中最长的递增子序列
最近邻点对O(n^2)和O(nlogn)算法
NlogN求逆序数对#include<iostream>#include<stdio.h>#include<string.h>#include<algorith
逆序对(归并排序)O(nlogn).cpp
北大POJ1836-Alignment【O(nlogn)】
北大POJ2533-Longest Ordered Subsequence【O(nlogn)】
北大POJ1804-Brainman【借助Mergesort求逆序数O(nlogn)】
2. 采用动态规划策略设计并实现算法,求解最长公共子序列问题。要求时间复杂性不超过O(m*n)。 三、贪心法 1.用贪心策略设计与实现一个贪心算法,求解背包问题。 2. 假设活动已经按照结束时间递增的次序排序。用贪心...
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)把小于基准值元素的子数列和大于基准值元素的子数列排序。
一些有关c的时间代码,请大家多多指教。都传一些好的资源。
希尔排序就是插入排序排序的一种简单改进,交换不相邻的元素以对数组的局部进行排序,以此来提升效率。 排序过程: 先让数组中任意间隔为 h 的元素有序,刚开始 h 的大小可以是 h = n / 2 接着让 h = n / 4,让 h ...