题目描述:
给定一个整型数组, 求这个数组的最长严格递增子序列的长度。 譬如序列1 2 2 4 3 的最长严格递增子序列为1,2,4或1,2,3.他们的长度为3。
输入:
输入可能包含多个测试案例。
对于每个测试案例,输入的第一行为一个整数n(1<=n<=100000):代表将要输入的序列长度
输入的第二行包括n个整数,代表这个数组中的数字。整数均在int范围内。
输出:
对于每个测试案例,输出其最长严格递增子序列长度。
样例输入:
4
4 2 1 3
5
1 1 1 1 1
样例输出:
2
1
老题目了,网上有经典的nlogn的算法,不过那个不好写。在二分的时候很容易写错。我用的是数状数组,不过步骤比较多。
我是先离散化,对输入的数据进行重新编号,
比如10 20 30
就变成了0 1 2了。
因为最长上升只子序列长度只和相对大小有关,所以这样做对结果是不会有影响的。
接下来就是从前往后DP了。
统计以当前元素结尾的最大上升子序列长度。
记为dp,本来在O(n*n)算法中是要把所有的0到i-1的DP值扫一遍,其本质上就是求解在第i个位置之前,以元素比a小的,最大值DP是多少。在这里,这个我们就可以用树状数组来做。查询一下比a小的这一段中最大值是多少,就可以了。然后把当前DP值插入到数组中a的位置。
我用了一些STL,所以写起来也不是很长。
#include <cstdio>
#include <string>
#include <cstring>
#include <ctime>
#include <cstdlib>
#include <map>
#include <queue>
#include <string>
#include <algorithm>
using namespace std;
typedef long long lld;
const int MAX=110000;
const int INF=1000000000;
int a[MAX];
int dcre[MAX];
int tree[MAX];
int query(int t)
{
int ret=0;
while(t)
{
if(tree[t]>ret)ret=tree[t];
t-=(-t)&t;
}
return ret;
}
void ins(int t,int v,int m)
{
while(t<=m)
{
if(v>tree[t])tree[t]=v;
t+=(-t)&t;
}
}
//start 提示:自动阅卷起始唯一标识,请勿删除或增加。
int main()
{
int T;
int n,m;
int last=0;
int i,j,k;
while(scanf("%d",&n)!=EOF)
{
for(i=0;i<n;i++)
{
scanf("%d",&a[i]);
dcre[i]=a[i];
}
sort(dcre,dcre+n);
m=unique(dcre,dcre+n)-dcre;
memset(tree,0,sizeof(int)*(m+2));
int ans=1,tmp;
for(i=0;i<n;i++)
{
a[i]=lower_bound(dcre,dcre+m,a[i])-dcre+1;
tmp=query(a[i]-1)+1;
if(tmp>ans)ans=tmp;
ins(a[i],tmp,m);
}
printf("%d\n",ans);
}
return 0;
}
分享到:
相关推荐
你的任务,就是对于给定的序列,求出最长上升子序列的长度。 输入样例 7 1 7 3 5 9 4 8 6 1 8 3 6 5 9 5 1 2 3 4 5 0 输出样例 4 4 5 提示 一,对输入字符串的处理 注意:这道题和其他题的输入输出不同,这题...
给定一个无序的整数数组,找到其中最长上升子序列的长度。 上升子序列指的是一个子序列,它的每个元素都严格大于它前面的元素。最长上升子序列则是指所有上升子序列中最长的那一个。 以下是使用动态规划求解最长...
2. 对于数组中的每个元素 `nums[i]`,我们遍历之前的元素 `nums[j]`,如果 `nums[i]` 大于 `nums[j]`,则 `dp[i] = max(dp[i], dp[j] + 1)`,即以 `nums[i]` 结尾的最长上升子序列的长度为之前所有比 `nums[i]` 小的...
最长上升子序列问题可以这样定义:给定一个无序的整数数组,任务是找到该数组中一个最长的子序列,使得这个子序列中的元素从左到右是严格递增的。这里的“子序列”是指从原数组中挑选出的一些元素,它们保持原序列中...
An,求这个序列中最长的递减子序列的长度M, 以及该序列可以划分成这种子序列的个数N 如序列: 300 250 252 275 200 138 245 折分成的子序列分别为 300 275 200 138 252 245 250 其中最长序列为: 300 275 200 138 ...
最长上升子序列(n·log(n)) Longest-Increasing-Subsequence(n·log(n)) 倍增法求最近公共祖先 Lowest-Common-Ancestor(Doubling) 朴素的矩阵乘法 Matrix-Multiplication(Naive) 归并排序 Merge-Sort 最小堆 ...
最长上升子序列 03-15 P695 岛屿的最大面积 03-16 面试题01.06 字符串压缩 03-17 P1160 拼写单词 03-18 P836 矩阵重叠 03-19 P409 最长回文串 03-20 面试题40 最小的k个数 03-27 P914 卡牌分组 03-28 P820 单词的...
1008的第一问和1009一样,第二问需要用到Dilworth分割定理:要求出最长不上升子序列的最少划分数,只需要求出这个序列中最长上升子序列的长度,这就转化成了和1009完全类似的问题。 1009 本质是找出序列中的一个最长...
O(n^2)的最长上升子序列 nlogn最长上升子序列 高精度 计算几何 Graham扫描法 两线段交点 凸多边形面积 半平面交 计算几何库 数据结构 闭散列法整数hash 开散列法整数hash 字符串hash 堆 二维树状数组 ...
leetcode 跳跃 ...电话号码的字母组合 四数之和 括号生成 合并K个排序链表 两两交换链表中的节点 K 个一组翻转链表 ...最长上升子序列 删除无效的括号 最佳买卖股票时机含冷冻期 戳气球 零钱兑换 打家劫舍 II
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...
最长上升子序列 最长回文子串 爬楼梯 零钱兑换 hash(哈希) 两数之和 linkedlist(链表) 两数相加 反转链表 回文链表 环形链表 环形链表II recurrence(递归) 岛屿最大面积 stack(栈) 两个栈实现队列 有效括号 string...
Leetcode:check_mark_button: Solutions to LeetCode by JavaScript.简单删除排序链表中的重复元素合并两个有序数组相同的...x-n二叉树的前序遍历lru 缓存机制最长上升子序列二叉树的中序遍历实现-trie-前缀树困难缺失
题:最长上升子序列 题解地址: LeetCode 第 315 题:计算右侧小于当前元素的个数 LeetCode 第 421 题:数组中两个数的最大异或值 题解地址: LeetCode 第 1079 题:活字印刷 题解地址: LeetCode 第 1080 题:根到...
lru cache leetcode Leetcode 参考: leetcode 经典题目解析&golang版代码 简单难度 中等难度 困难难度 ...完全平方数 ...最长上升子序列 [动态规划] 221. 最大正方形 [动态规划] 53. 最大子序和 [动态规划]
有界最大值的子数组数 范围总和查询可变 K 逆对数组 在上升的水中游泳 帕斯卡三角形 从源头到目的地的所有路径 匹配子序列数 反向链表 II 越界路径 越界路径 糖果 删除字符串中所有相邻的重复项 阿姆斯壮数 最大连续...
1.LIS (最长上升子序列) 2.有依赖的背包 (附属关系) 3.最长公共子序列(LCS) 4.树形DP 5.状压DP-斯坦纳树 6.背包 7.dp[i]=min(dp[i+1]…dp[i+k]),multset 博弈: 1.NIM博弈 (n堆每次最少取一个) 2.威佐夫博弈(两堆...
leetcode算法题主函数如何写 one_algorithm_one_day ...[最长上升子序列] # 1. 求两个已排序数组的中位数 There are two sorted arrays nums1 and nums2 of size m and n respectively. Find the median of the two so
最大上升子序列 最小Ascii删除距离 最长回文串 三角形最短路径和 正则表达式匹配 买卖股票问题 买卖股票最佳时机I 买卖股票最佳时机II 买卖股票最佳时机III 买卖股票最佳时机IV 买卖股票含手续费 买卖股票含冷冻期 ...