[编程题]最长递增子序列
- 热度指数：6513 时间限制：C/C++ 2秒，其他语言4秒 空间限制：C/C++ 256M，其他语言512M
- 算法知识视频讲解
给定数组arr，设长度为n，输出arr的最长递增子序列。（如果有多个答案，请输出其中字典序最小的）
输入描述:
输出两行，第一行包括一个正整数n（n<=100000），代表数组长度。第二行包括n个整数，代表数组arr。
输出描述:
输出一行。代表你求出的最长的递增子序列。
示例1
输入
9 2 1 5 3 6 4 8 9 7
输出
1 3 4 8 9
示例2
输入
5 1 2 8 6 4
输出
1 2 4
说明
其最长递增子序列有3个，（1，2，8）、（1，2，6）、（1，2，4）其中第三个字典序最小，故答案为（1，2，4）
备注:
时间复杂度，空间复杂度
。
#include<bits/stdc++.h>
using namespace std;
int getIndex(vector<int>& v,int x)
{
int res = -1;
int left = 0;
int right = v.size()-1;
while(left<=right)
{
int mid = (left+right)>>1;
if(v[mid]>=x)
{
res = mid;
right = mid-1;
}
else left = mid + 1;
}
return res;
}
vector<int> getLIS(vector<int>&v,vector<int>& dp)
{
// maxLen
int maxLen = 0;
int index = 0;
for(int i=0;i<dp.size();++i)
{
// 字典序的话，这里要取>=
if(dp[i]>=maxLen)
{
maxLen = dp[i];
index = i;
}
}
//cout<<"maxlen "<<maxLen<<" index"<<index<<endl;
vector<int>ans(maxLen);
ans[--maxLen] = v[index];
vector<int>temp;
for(int i=index;i>=0;--i)
{
if(v[i]<v[index] && dp[i]==dp[index]-1)
{
ans[--maxLen] = v[i];
index = i;
}
}
return ans;
}
int main()
{
int n;
cin>>n;
vector<int>v(n);
for(int i=0;i<n;++i) cin>>v[i];
vector<int>record;
// dp[i] 以v[i]结尾的序列的最大长度
vector<int>dp(n);
dp[0] = 1;
record.push_back(v[0]);
//int use = -1;
for(int i=1;i<n;++i)
{
int l = getIndex(record,v[i]);
if(l != -1)
{
record[l] = v[i];
dp[i] = l + 1;
}
else
{
record.push_back(v[i]);
dp[i] = record.size();
}
}
//for(int i:dp)
// cout<<i<<endl;
vector<int> ans = getLIS(v,dp);
for(int i : ans)
cout<<i<<" ";
}
发表于 2020-02-09 18:12:14
回复(1)
经典的动态规划问题，先用二分查找求出dp，复杂度为O(lgn)。打印数组，从后往前打。字典序打印判断条件为>=，打印第一次符合长度的判断条件为>
import java.util.*;
import java.io.*;public class Main{
public static void main(String[] args)throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
String[] s = br.readLine().split(" ");
int[] arr = new int[n];
for(int i = 0;i<n;i++){
arr[i] = Integer.parseInt(s[i]);
}
int[] res = getResult(arr);
for(int j = 0 ;j<res.length;j++){
System.out.print(res[j]+" ");
}
}
public static int[] getResult(int[] arr){
if(arr==null||arr.length==0) return arr;
int[] dp = getdp(arr);
return getList(arr,dp);
}
public static int[] getdp(int[] arr){
int[] dp = new int[arr.length];
int[] ends = new int[arr.length];
ends[0] = arr[0];
dp[0] = 1;
int right = 0;
int l = 0 ;
int r = 0;
int m = 0;
for(int i = 1;i <arr.length;i++){
l = 0;
r= right;
while(l<=r){
m = (l +r )/2;
if(arr[i]<ends[m]){
r = m-1;
}else{
l = m+1;
}
}
right = Math.max(right,l);
ends[l] = arr[i];
dp[i] = l+1;
}
return dp;
}
public static int[] getList(int[] arr, int[]dp){
int len = 0 ;
int index = 0 ;
for(int i = 0 ; i <dp.length;i++){
if(dp[i]>=len){
len = dp[i];
index = i;
}
}
int[] result = new int[len];
len--;
result[len] = arr[index];
for(int i = index ; i >=0;i--){
if(arr[i]<arr[index] && dp[i] == dp[index] -1){
len--;
result[len] = arr[i];
index = i ;
}
}
return result;
}
}
发表于 2019-08-18 22:51:34
回复(0)
优化到O(nlogn)，主要是在求dp[i]时，不是单纯地遍历[0...i-1]，而是通过二分查找法。原始序列是无序的，必须构建一个辅助数组ends，ends[i]表示长度为i+1的递增子序列的最小的结束元素。听起来还是很抽象。以数组[1 2 8 6 4 5]为例：
首先ends[0] = 1, 其有效范围设定为right = 0，表示right位置及之前的元素是有效的，后续只和该范围的元素比较。
首先ends[0] = 1, 其有效范围设定为right = 0，表示right位置及之前的元素是有效的，后续只和该范围的元素比较。
遍历至arr[1]时，其值为2，二分查找ends有效范围，其插入位置为1，扩展ends范围，令ends[1] = 2, right = 1。
遍历至arr[2]时，其值为8，二分查找ends有效范围，其插入位置为2，扩展ends范围，令ends[2] = 8, right = 2。
遍历至arr[3]时，其值为6，二分查找ends有效范围，其插入位置为2，无须扩展ends，令ends[2] = 6, right不变。处理到此时，ends[i]的涵义就很明朗了，此时6是长度为3的递增子序列的最小结束元素，替换了之前的8。既然同样是构成长度为3的递增子序列，以6结束必然比之前的8结束更有可能在后续的遍历中组成更长的递增子序列。
遍历至arr[4]时，ends[2] = 4, right不变。
最后的5是我在原题的例子上追加的，正是因为此前的长度为3的递增子序列的最小结束元素是4，5的出现才能构成更长的递增子序列。而此前的8或6则不行。
这道题的关键是设计ends数组。上面的ends最终结果曾给我错觉，以为ends就是最后的最长递增子序列，然而并不是，譬如
9
2 1 5 3 6 4 8 9 7
最后的ends = [1 3 4 7 9]
PS：ends数组的设计是从左神的书上看的。
9
2 1 5 3 6 4 8 9 7
最后的ends = [1 3 4 7 9]
PS：ends数组的设计是从左神的书上看的。
#include <iostream>
(720)#include <vector>
using namespace std;
vector<int> getSubSeqOnlogn(vector<int>& arr) {
int n = arr.size();
vector<int> dp(n, 1);
vector<int> ends(n, 0);//ends[i]表示长度为i+1的递增子序列的最小的结束元素
ends[0] = arr[0];
int right = 0; //ends的有效范围[0...right]
int l = 0;
int r = 0;
int maxLen = 1; //最长递增子序列的长度
int maxInd = 0; //最长递增子序列结束元素的索引
for(int i = 1; i < n; i++) {
l = 0;
r = right;
while(l <= r) {//查找arr[i]在ends有效范围上的插入位置，如果比其元素都大，则ends有效范围扩展
int mid = (l + r) >> 1;
if(arr[i] > ends[mid]) {
l = mid + 1;
}
else {
r = mid - 1;
}
}
right = max(right, l); //ends有效范围可能会扩展
ends[l] = arr[i]; //更新长度为i+1的递增子序列的结束元素
dp[i] = l + 1; //arr[i]为结束元素的最长递增子序列的长度
if(dp[i] >= maxLen) {//更新最大长度，由于题目有字典序最小的要求，=是必须的
maxLen = dp[i];
maxInd = i;
}
}
vector<int> ans(maxLen);
for(int i = maxInd; i >= 0; i--) {
if(dp[i] == maxLen) {
ans[--maxLen] = arr[i];
}
}
return ans;
}
int main() {
int n;
cin >> n;
vector<int> arr(n);
for(int i = 0; i < n; i++) {
cin >> arr[i];
}
vector<int> ans = getSubSeqOnlogn(arr);
for(int i = 0; i < ans.size(); i++) {
cout << ans[i] << " "; //题目对最后的空格很宽容，就这样吧
}
return 0;
}
编辑于 2020-04-21 02:22:56
回复(0)
题目要求时间复杂度为O(logN)，需要使用左神书上构建单调数组ends的方法，这个方法我已经在第29题“信封嵌套问题”中做了解释，本题就不多说了。本题主要想讨论一下拿到最长自增子序列的长度后怎么还原这个最长递增子序列。与单纯求长度的流程稍有不同，如果需要还原子序列，我们还需要一个变量maxIdx来记录当取得最长递增子序列的长度值时，是以原数组中哪个位置的元素结尾的。我们通过这个位置来进行倒推，就能逐步还原出整个最长自增子序列。流程如下：
- 准备一个长度为maxLen的数组，这时候我们要填最后一个元素，由于arr[maxIdx]是最长递增子序列的最后一个元素，所以先把它填进数组的末尾res[maxLen - 1]。然后maxLen自减（因为已经填完一个元素了）继续往maxIdx的左边前遍历dp数组。
- 如果遇到dp[i]=maxLen，说明遇到了一个递增子序列长度为maxLen的结尾，再次把arr[i]填入数组的末尾res[maxLen - 1]。然后maxLen自减继续往前遍历dp数组，周而复始就能够填完整个数组。
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
String[] strArr = br.readLine().split(" ");
int[] arr = new int[n];
for(int i = 0; i < n; i++){
arr[i] = Integer.parseInt(strArr[i]);
}
int[] dp = new int[n];
int[] ends = new int[n];
dp[0] = 1;
ends[0] = arr[0];
int tail = 0; // 有效区域末尾
int maxLen = 1, maxIdx = 0; // 最长递增子序列长度和index
for(int i = 1; i < n; i++){
int index = lowerbound(ends, 0, tail, arr[i]);
dp[i] = index + 1; // 以i结尾的最长递增子序列长度为index+1
ends[index] = arr[i];
if(index > tail){
tail++; // 有效区扩充
}
if(dp[i] >= maxLen){
maxLen = dp[i];
maxIdx = i;
}
}
// 还原字典序最小的最长递增子序列
int[] increasingSeq = new int[maxLen];
for(int i = maxIdx; i >= 0; i--){
// 从后往前更新，遇到递增子序列长度为maxLen的arr[i]就更新结尾位置，然后把maxLen缩短
if(dp[i] == maxLen){
increasingSeq[--maxLen] = arr[i];
}
}
for(int i = 0; i < increasingSeq.length; i++){
System.out.print(increasingSeq[i] + " ");
}
}
private static int lowerbound(int[] arr, int L, int R, int target) {
int left = L, right = R;
int index = R + 1;
while(left <= right){
int mid = left + ((right - left) >> 1);
if(arr[mid] < target){
left = mid + 1;
}else{
index = mid;
right = mid - 1;
}
}
return index;
}
}
编辑于 2021-12-10 10:56:26
回复(1)
#include <bits/stdc++.h>
using namespace std;
int main(){
int n, l=0, k;
scanf("%d", &n);
int a[n], b[n], dp[n]={0};
for(int i=0;i<n;i++){
scanf("%d", &a[i]);
int t = lower_bound(b, b+l, a[i]) - b;
if(t == l){
b[l++] = a[i];
dp[i] = l;
k = i;
}else{
b[t] = a[i];
dp[i] = t+1;
if(dp[i] == l)
k = i;
}
}
int r[l], m=l;
r[--l] = a[k];
for(int i=k;i>=0;i--){
if(a[i]<a[k] && dp[i]==dp[k]-1){
r[--l] = a[i];
k = i;
}
}
for(int i=0;i<m;i++)
printf("%d ", r[i]);
}
发表于 2020-06-08 21:35:53
回复(0)
import java.util.*;
import java.io.*;
//这里用到了java自带的二分查找法，当然可以自己写，int binarySearch(int []arr,int s, int e, int key )。左闭右开。该方法要求数组非严格单调增。
//该方法自动查找到数组中第一个等于key的值的索引（假设arr中有key），返回该索引；如果没有则会找到第一个大于key的值的索引x。并返回: - x - 1。
//若数组中元素均小于key则返回: - len - 1。也就是可以利用返回值找到一个大于或等于key的值的索引。
//最好自己画图看看，很容易看出来。给一个设计好的测试用例 { 9,10,11,12, 8, 4, 15, -5, -4, -3, 7 }。
public class Main{
public static void main(String[] args)throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
String[] s = br.readLine().split(" ");
int[] arr = new int[n];
for(int i = 0;i<n;i++){
arr[i] = Integer.parseInt(s[i]);
}
lengthOfLIS(arr);
}
public static int lengthOfLIS(int[] nums){
// 1.minTail[i]用来记录所有长度为i+1的递增序列中，末尾的最小值。可以用反正法证明minTail数组必然是一个单调递增数组。下面关键步骤是通过遍历nums数组逐渐的得到minTail
// 2.dp[i] 记录以数组nums中第i个数字结尾的LIS的长度。
// 3.通多上面两个数组求出最小LIS
int[] minTail = new int[nums.length];//minTail数组真实长度就是LIS长度，不确定，所以创建了一个和nums等长的数组，初始值均为0。
int[] dp = new int[nums.length];//数组dp长度等于nums长度
int len = 0;//表示minTail目前用到的长度
for (int l = 0; l < nums.length; l++){// 随着数组的遍历不断地跟新minTail
// 搜索第一个大于nums[l]的数的位置。
int i = Arrays.binarySearch(minTail, 0, len, nums[l]);
while(i>=0){//若查找到minTail中包含nums[l],接着二分查找直到找到第一个大于nums[l]的数
i = Arrays.binarySearch(minTail, i+1, len, nums[l]);
}
i = -i - 1;//得到大于nums[l]的第一个值的索引
// 已有序列都小于num
if (i == len){
len++;
}
// 替换掉第一个大于或等于nums[l]的数,也就是说长为i+1的递增子序列最小值可以是更小的nums[l]。如果数组中没有比num大的数则num添加到末尾。
minTail[i] = nums[l];
dp[l] = i + 1;
}
// 下面代码用来找到按照字母表排序最小的最长递增子序列
int[] res = new int[len];
int index = res.length - 1;
int next = Integer.MAX_VALUE;
for (int k = nums.length - 1; k >= 0; k--){
if (nums[k] <= next && dp[k] == index + 1){//满足该条件求得的序列就是目标LIS。假设已知LIS最后一个数字（其实就是minTail中最后一个非0值
//通过该判断求LIS前一个数值？（首先该条件为nums[k]是LIS倒数第二个数值的充分条件，但还需证明由该条件得到的LIS按字典排序最小）。假设除了k满足该条件，
//还有i，j...满足，那么i，j...不可能在k之后（因为倒着遍历nums），所以推出num[i,j,...]必然大于nums[k]。绝不可能小于或者等于，否则可以推出dp[k]==index+2
res[index] = nums[k];
next = res[index];
index--;
}
}
StringBuilder sb = new StringBuilder();
for (int val : res)
sb.append(val).append(" ");
System.out.println(sb.toString());
return len;
}
}
编辑于 2020-02-10 22:44:11
回复(0)
测试已通过。想了好久怎么找到最小的字典子序列。最后发现只要是相应的dp[]值相同的元素，最右边的那个的值最小，所以直接划到最右边开始向左遍历就可以了，参见getList子函数
#include <iostream>
#include <vector>
using namespace std;
int maxNumber(int a, int b);
vector<int> getDP(vector<int> arr);
vector<int> getList(vector<int> arr, vector<int> dp);
int main()
{
int CntOfNumbers = 0;
int numberOfArray = 0;
vector<int> array;
vector<int> result;
vector<int> dp;
//输入数组大小
cin >> CntOfNumbers;
//数组元素
for(int i = 0; i < CntOfNumbers;i++)
{
cin >> numberOfArray;
array.push_back(numberOfArray);
}
//dp[i]表示遍历到arr[i]时，arr[0...i]组成的最长子序列长度
dp = getDP(array);
result = getList(array, dp);
int length = result.size();
for(int i = 0; i < length; i++)
{
cout << result[i] << " ";
}
return 0;
}
int maxNumber(int a, int b)
{
return a > b ? a : b;
}
vector<int> getDP(vector<int> arr)
{
int length = arr.size();
vector<int> dp(length, 0);
vector<int> end(length, 0);
//有效区的右边界会更新
int right = 0;
int l = 0, m = 0, r = 0;
end[0] = arr[0];
dp[0] = 1;
//开始对后面的数字用二分法更新end数组和dp数组
for(int i = 1; i < length; i++)
{
l = 0;
r = right;
//找到end中最左边大于或等于arr[i]的位置，或者直接大于end最右边的数,l走到了right+1处
while(l <= r)
{
m = (l + r)/2;;
if(arr[i] > end[m])
l = m + 1;
else
r = m - 1;
}
//扩大有效区
right = maxNumber(right, l);
//更新数组
end[l] = arr[i];
dp[i] = l + 1;
}
return dp;
}
vector<int> getList(vector<int> arr, vector<int> dp)
{
int length = arr.size();
//最长子序列的长度和对应的下标
int len = 0;
int index = 0;
for(int i = 0; i < length; i++)
{
//滑到最右边那个最大的dp[i]和下标
//因为当dp相同时，最右边那个数最小，所以接下来第一个找到符合要求的数就可以直接存入数组中
if(dp[i] >= len)
{
len = dp[i];
index = i;
}
}
//开始寻找最小值的最长子序列
vector<int> list(len, 0);
//先放置最后那个数
list[--len] = arr[index];
//从后往前遍历
for(int i = index - 1; i >= 0; i--)
{
//要满足两个条件
if(arr[i] < arr[index] && dp[i] == (dp[index] - 1))
{
list[--len] = arr[i];
index = i;
}
}
return list;
}
发表于 2019-08-19 20:35:17
回复(0)
#include<bits/stdc++.h>
using namespace std;
int a[100001], endS[100001];
int main(){
int n; cin >> n;
for(int i = 0; i < n; i++)cin>>a[i];
vector<int>high;
for(int i = 0; i < n; i++){
auto it = lower_bound(high.begin(), high.end(), a[i]);
if(it == high.end())high.push_back(a[i]), endS[i] = high.size();
else *it = a[i], endS[i] = it - high.begin() + 1;
}
vector<int>ans;
int lenAns = high.size();
for(int i = n - 1; i >= 0; i--){
if(endS[i] == lenAns)ans.push_back(a[i]), lenAns--;
}
reverse(ans.begin(), ans.end());
for(auto i : ans)cout << i << ' ';
}
using namespace std;
int a[100001], endS[100001];
int main(){
int n; cin >> n;
for(int i = 0; i < n; i++)cin>>a[i];
vector<int>high;
for(int i = 0; i < n; i++){
auto it = lower_bound(high.begin(), high.end(), a[i]);
if(it == high.end())high.push_back(a[i]), endS[i] = high.size();
else *it = a[i], endS[i] = it - high.begin() + 1;
}
vector<int>ans;
int lenAns = high.size();
for(int i = n - 1; i >= 0; i--){
if(endS[i] == lenAns)ans.push_back(a[i]), lenAns--;
}
reverse(ans.begin(), ans.end());
for(auto i : ans)cout << i << ' ';
}
编辑于 2023-02-07 15:09:24
回复(0)
//二分查找+贪心
#include "bits/stdc++.h"
using namespace std;
int midsearch(int target,vector<int>& arr1,vector<int>& arr){
//arr1中第一个对应到arr中的值大于等于target的下标
int l=0,r=arr1.size();
int mid;
while(l<r){
mid=(l+r)>>1;
if(arr[arr1[mid]]==target) {
while(mid-1>=0&&arr[arr1[mid-1]]==target)
mid--;
return mid;
}
else if(arr[arr1[mid]]>target) r=mid;
else if(arr[arr1[mid]]<target) l=mid+1;
}
return l;
}
int main()
{
//贪心+二分查找可以求出最大递增子序列长度
//怎么得到最大递增子序列？
//arr1[i]表示递增长度最大长度为i时，使第i个值最小的arr的下标
//dp[i]表示arr[i]作为其中一个值时，它的的前一个值的下标
int len;cin>>len;
vector<int> arr(len);
for(int i=0;i<len;i++) cin>>arr[i];
vector<int> dp(len,-1);
vector<int> arr1;
arr1.push_back(0);
for(int i=1;i<len;i++){
int target=arr[i];
if(target>arr[arr1.back()]){
dp[i]=arr1.back();
arr1.push_back(i);
}
else{
int t=midsearch(target, arr1,arr);
arr1[t]=i;
if(t>0) dp[i]=arr1[t-1];
}
}
int len1=arr1.size();
vector<int> ret(len1,0);
ret[len1-1]=arr[arr1.back()];
int j=len1-2;
int last=dp[arr1.back()];
//for(int i=0;i<len;i++)cout<<dp[i];
while(j>=0){
ret[j]=arr[last];
j--;
last=dp[last];
}
for(int i=0;i<len1;i++){
cout<<ret[i]<<' ';
}
return 0;
}
发表于 2022-07-09 16:42:34
回复(0)
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
public static void longestIncreasingSequence(int[] num) {
int[] arr = new int[num.length];
int[] dp = new int[num.length];
int sum = 0;
int idx;
for (int i = 0; i < num.length; ++i) {
idx = Arrays.binarySearch(arr, 0, sum, num[i]);
while (idx > 0) {
idx = Arrays.binarySearch(arr, idx + 1, sum, num[i]);
}
if (sum == -idx - 1) {
sum++;
}
arr[-idx - 1] = num[i];
dp[i] = -idx;
}
int[] res = new int[sum];
int index = res.length - 1;
int next = Integer.MAX_VALUE;
for (int k = num.length - 1; k >= 0; --k) {
if (num[k] <= next && dp[k] == index + 1) {
res[index] = num[k];
next = res[index];
if ((--index) < 0) {
break;
}
}
}
StringBuilder builder = new StringBuilder("");
for (int re : res) {
builder.append(re).append(" ");
}
System.out.println(builder.toString());
}
public static void main(String[] args) throws IOException {
BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(bufferedReader.readLine());
String[] str = bufferedReader.readLine().split(" ");
int[] num = new int[n];
for (int i = 0; i < n; ++i) {
num[i] = Integer.parseInt(str[i]);
}
longestIncreasingSequence(num);
}
}
发表于 2020-03-23 18:27:01
回复(0)
import java.util.*;
import java.io.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));
int n = Integer.parseInt(in.readLine());
String[] t = in.readLine().split(" ");
int[] nums = new int[n];
for (int i = 0; i < n; i++) nums[i] = Integer.parseInt(t[i]);
int[] q = new int[n + 10], f = new int[n + 10];
int len = 0, idx = 0;
for (int i = 0; i < n; i++) {
int l = 0, r = len;
while (l < r) {
int mid = l + r + 1 >> 1;
if (q[mid] < nums[i]) l = mid;
else r = mid - 1;
}
q[l + 1] = nums[i];
f[i] = Math.max(f[i], l + 1);
if (f[i] >= len) {
len = f[i];
idx = i;
}
}
int[] ans = new int[len];
for (int i = idx; i >= 0; i--) {
if (f[i] == len) ans[--len] = nums[i];
}
for (int i = 0; i < ans.length; i++) out.write(ans[i] + " ");
out.flush();
}
}
发表于 2022-01-27 11:12:21
回复(0)
def solution(nums):
stack = []
pre_idx = [-1] * len(nums)
for idx, num in enumerate(nums):
if not stack&nbs***bsp;num > nums[stack[-1]]:
stack.append(idx)
pre_idx[idx] = stack[-2] if len(stack) > 1 else -1
else:
l, r = 0, len(stack) - 1
loc = r
while l <= r:
mid = (l + r) // 2
if nums[stack[mid]] >= num:
loc = mid
r = mid - 1
else:
l = mid + 1
stack[loc] = idx
pre_idx[idx] = stack[loc - 1] if loc >0 else -1
idx = stack[-1]
res = []
while idx != -1:
res = [str(nums[idx])] + res
idx = pre_idx[idx]
return res
# return [str(item) for item in val_idx]
n = map(int, input().strip())
array = list(map(int, input().strip().split()))
# print(array)
res = solution(array)
print(' '.join(res)) stack保存的是从左到右的递增值，但有可能其在原数组中的index顺序并不合法
因此需要另外一个pre_idx来辅助标记以nums[stack[k]]为结尾的序列，其前一个序列在什么位置上，即pre_idx[k]
然后从右往左重建最长序列
发表于 2021-10-14 21:47:56
回复(0)
字典序要读到最后，即>= 往回读的时候读第一个
#include<bits/stdc++.h>
using namespace std;int main(){
int n;
cin>>n;
vector<int>arr(n),dp(n),end(n);
int t,right=0,left=0;;
cin>>t;
arr[0]=t;
end[0]=t;
dp[0]=0;
for(int i=1;i<n;i++){
cin>>t;
arr[i]=t;
int leftk=left,rightk=right;
while(leftk<=rightk){
int mid=leftk+(rightk-leftk);
if(end[mid]<t){
leftk=mid+1;
}
else if(end[mid]==t){
leftk=mid+1;
}
else if(end[mid]>t){
rightk=mid-1;
}
}
if(rightk==-1){
end[0]=t;
dp[i]=0;
}
else {
if(rightk==right){
right++;
}
end[rightk+1]=t;
dp[i]=rightk+1;
}
}
int index=0;
int num=0;
int length=0;
for(int i=0;i<n;i++){
if(length<=dp[i])
{ length=dp[i];
index=i;
num=arr[i];
}
}
vector<int>res(length+1);
res[length]=(num);
for(int i=index;i>=0;i--){
if(dp[i]==length-1&&arr[i]<=num){
num=arr[i];
res[length-1]=arr[i];
length--;
}
}
/*
for(int i=0;i<n;i++){
cout<<arr[i]<<" ";
}
cout<<endl;
for(int i=0;i<n;i++){
cout<<end[i]<<" ";
}
cout<<endl;
for(int i=0;i<n;i++){
cout<<dp[i]<<" ";
}
cout<<endl;
*/
for(int i=0;i<res.size();i++){
cout<<res[i]<<" ";
}
cout<<endl;
}
发表于 2021-01-05 15:36:37
回复(0)
Short C++ DP solution with time complexity O(nlogn) and space O(n)
#include <iostream>
#include <algorithm>
#include <string.h>
#include <vector>
using namespace std;
const int MAXN = 1e5 + 10;
int n;
int arr[MAXN], pre[MAXN];
int main(){
cin >> n;
for(int i = 0; i < n; i ++) cin >> arr[i];
vector<int> dp = {-1};
for(int i = 0; i < n; i ++){
int lp = 0, rp = dp.size() - 1;
while(lp < rp){
int mid = lp + (rp - lp + 1) / 2;
int idx = dp[mid];
if(idx == -1 || arr[i] > arr[idx])
lp = mid;
else
rp = mid - 1;
}
if(lp == dp.size() - 1)
dp.push_back(i);
else
dp[lp + 1] = i;
pre[i] = dp[lp];
}
vector<int> rnt;
int pt = dp.back();
while(pt != -1){
rnt.push_back(arr[pt]);
pt = pre[pt];
}
for(int i = rnt.size() - 1; i >= 0; i --)
cout<<rnt[i]<<" ";
cout<<endl;
return 0;
}
编辑于 2020-08-27 15:00:30
回复(0)
C++解法，动态规划+贪心法
这题和书上不一样，多了个要求，输出的子序列必须字典序最小。求最大子序列长度倒是非常迅速。然而通过辅助数组来获得字典序最小的子序列，我已内牛满面。
思路分析：
求dp数组的步骤和书上是差不多的，这里用自己写的二分来找的。问题在于得到dp数组之后，怎么快速获得字典序最小的子序列。暴力法就是双层循环，复杂度n²，瞬间凉凉。
上点数据，看起来具体点
index: 0 1 2 3 4 5 6 7 8
num: 2 1 5 3 6 4 8 9 7
dp: 1 1 2 2 3 3 4 5 4
index就是索引，为了看着方便写的
num是给定的数组
dp[i]是index为i的元素结尾时，最长递增子序列长度。
以这个题为例，得到dp后，我们很容易可以得到res的长度是5.
现在的问题，就是往res[0]......res[4]上填数，完事儿要保证这个填完之后字典序最小且是可行解。
举个不可行的例子，res[3]代表长度为4的递增子序列，结尾有两个值，num[6]=8, num[8]=7，看起来，7比8小，但是这里不能选7，因为7作为res[3]的话，res[4]就凉凉了，因为7之后没有元素比7大，只能得到一个长度为4的递增子序列，它不是最长的。
这里用的贪心法，限制最右侧查找限制，只能在限制的左侧查找。方法是从右往左找出限制位置，再从左往右找到最小数字。
使用一个辅助数组limit，limit[i]表示dp[k]=i的限制位置。下面具体说一下
最长递增子序列为5，最右侧的5在index=7的位置，limit[5] = 7
从index=7往左找， 最右侧的4在index=6的位置，limit[4] = 6
同理，limit[3]=5, limit[2]=3, limit[1]=1
limit: [0, 1, 3, 5, 6, 7]
这个辅助数组，能保证找到子序列的有效性。直观理解就是，从dp[s]=5开始往左找的，保证了这个子序列一定能到达dp[s]=5的位置，就是最长的。完事儿再从右向左继续找到各个位置的限制点。这些限制位置会作为查找最优解的右边界。左边界就是我们顺查时取到的每个最优点。
#include <bits/stdc++.h>
using namespace std;
// 得到dp数组
static void getdp(vector<int> &v, vector<int> &dp, int &maxlen){
int sz = v.size();
vector<int> ends(sz, 0);
dp[0] = 1;
ends[0] = v[0];
int right = 1;
for(int i=1;i<sz;i++){
int fleft = 0;
int fright = right;
while(fleft < fright){
int mid = fleft + ((fright-fleft)>>1);
if(ends[mid] < v[i])
fleft = mid + 1;
else
fright = mid;
}
dp[i] = fleft + 1;
ends[fleft] = v[i];
if(fright == right)
++right;
}
maxlen = right;
return ;
}
static void getminseq(vector<int> &v, vector<int> &res, vector<int> &dp, int maxlen){
int find = maxlen;
int sz = v.size();
vector<int> limit(maxlen+1, 0);
int pos = maxlen;
// 构造limit，查找的右边界
for(int i=sz-1;i>=0;--i){
if(dp[i] == find){
limit[pos--] = i;
find--;
}
}
pos = 0;
int left = 0, right = 0, minpos=0, minvalue=0;
for(int target=1;target<=maxlen;target++){
minvalue=INT_MAX;
left = minpos; // 上一次的最优解位置作为左边界
right=limit[target]; // limit作为右边界
for(int k=left;k<=right;k++){ // 范围内查找最小元素
if(dp[k] == target){
if(v[k] < minvalue){
minvalue = v[k];
minpos = k;
}
}
}
res[pos++] = minvalue;
}
return;
}
int main(){
int n;
cin>>n;
vector<int> v(n);
for(int i=0;i<n;i++)
cin>>v[i];
vector<int> dp(n, 0);
int maxlen;
getdp(v, dp, maxlen);
vector<int> res(maxlen, 0);
getminseq(v, res, dp, maxlen);
for(int num : res)
cout<<num<<" ";
return 0;
}
发表于 2020-08-09 18:54:27
回复(0)
#include <iostream>
using namespace std;
#define N 100000
int arr[N];
int dp[N];
int my_ends[N];
int record[N];
int main()
{
int n;
cin>>n;
for(int indx=0;indx<n;++indx)
{
cin>>arr[indx];
}
// dp process
dp[0]=1;
int right=0;
my_ends[0]=arr[0];
int l=0;
int r=0;
int m=0;
int dp_max_rec=1;
int dp_max_indx=0;
for(int i=1;i<n;++i)
{
l=0;
r=right;
while(l<=r)
{
m=(l+r)/2;
if(arr[i]>my_ends[m])
l=m+1;
else
r=m-1;
}
dp[i]=l+1;
my_ends[l]=arr[i];
if(l>right)
right=l;
if(dp[i]>=dp_max_rec)
{
dp_max_rec=dp[i];
dp_max_indx=i;
}
}
record[dp_max_rec-1]=dp_max_indx;
int cur=dp_max_rec-1;
for(int indx=dp_max_indx-1;indx>=0;--indx)
{
if(cur<=0)
{
break;
}
if(dp[indx]==dp[record[cur]]-1&&arr[indx]<arr[record[cur]])
{
--cur;
record[cur]=indx;
continue;
}
if(dp[indx]==dp[record[cur]]&&arr[indx]<arr[record[cur]])
{
record[cur]=indx;
continue;
}
if(dp[indx]>dp[record[cur]])
{
if(arr[indx]<arr[record[dp[indx]-1]])
{
cur=dp[indx]-1;
record[cur]=indx;
continue;
}
}
}
for(int indx=0;indx<dp_max_rec;++indx)
{
cout<<arr[record[indx]];
if(indx==dp_max_rec-1)
cout<<'\n';
else
cout<<' ';
}
return 0;
}
发表于 2020-07-21 19:52:11
回复(0)
有没有大神帮忙看看我这个为啥100000的时候通过率是百分百之4.7 我彻底懵了 我看了一下 跟正确答案相比dp数组是对的啊 是不是根据dp数组求lis的时候出问题了呢 在此感谢大家的帮助
#include<iostream>
(720)#include<algorithm>
using namespace std;
int *arr;
int *dp;
int *bin;
int *lis;
//二分查找利用bin数组能优化dp数组的计算速度
int BinarySearch(int *bin, int len, int n){
int left = 1;
int right = len;
while (left < right){
int mid = (left + right) / 2;
if (bin[mid] > n){
right = mid;
}
else{
left = mid + 1;
}
}
return right;
}
int getResult1(int n){
dp[0] = 1;
bin[1] = arr[0];
int index = 1;
for (int i = 1; i < n; i++){
if (arr[i] > bin[index]){
bin[++index] = arr[i];
dp[i] = index;
}
else{
int temp = BinarySearch(bin, index, arr[i]);
bin[temp] = arr[i];
dp[i] = temp;
}
}
return index;
}
int main(){
int n;
cin >> n;
arr = new int[n];
dp = new int[n + 1];
bin = new int[n + 1];
for (int i = 0; i < n; i++){
cin >> arr[i];
}
//根据dp数组计算lis数组
int ans = getResult1(n);
int length = ans;
lis = new int[ans];
int index = 0;
for (int i = n - 1; i >= 0; i--){
if (dp[i] == ans){
lis[--ans] = arr[i];
index = i;
break;
}
}
index--;
for (int i = index; i >= 0; i--){
if (dp[i] == ans){
lis[--ans] = arr[i];
}
}
for (int i = 0; i < length; i++){
cout << lis[i] << endl;
}
delete[] arr;
delete[] dp;
delete[] bin;
delete[] lis;
return 0;
}
发表于 2020-04-22 17:01:58
回复(0)
//这个本地所有测试样例都可以通过，牛客超时，应该需要用二分
#include<cstdio>
#include<vector>
using namespace std;
vector<int> dp;
vector<int> v;
int choice[100010];
vector<int> maxpath;
int main() {
int n;
scanf("%d", &n);
dp.resize(n);
v.resize(n);
maxpath.clear();
fill(choice, choice + 100010, -1);
//choice.resize(n);
for (int i = 0; i < n; ++i) {
scanf("%d", &v[i]);
dp[i] = 1;
}
int mmax = 1, mmaxi = 0;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < i; ++j) {
if (v[j] < v[i]) {
if (dp[j] + 1 > dp[i])
{
dp[i] = dp[j] + 1;
choice[i] = j;
}
else if (dp[j] + 1 == dp[i]) {
if (v[choice[i]] >=v[j]) {
choice[i] = j;
}
}
}
}
if (mmax <= dp[i]) {
mmax = dp[i];
mmaxi = i;
}
}
while (mmaxi != -1) {
maxpath.push_back(mmaxi);
mmaxi = choice[mmaxi];
}
int flag = 0;
for (int i = maxpath.size() - 1; i >= 0; --i) {
if (flag == 0) {
printf("%d", v[maxpath[i]]);
flag = 1;
}
else {
printf(" %d", v[maxpath[i]]);
}
}
return 0;
}
编辑于 2020-04-21 17:18:04
回复(1)
我这个超时了 有没有大佬帮改一下
#include<bits/stdc++.h>
using namespace std;int main(){
int n(0),k(0);
int a[100001];
int dp[100001];
scanf("%d",&n);
for(int i(0);i < n;i++){
scanf("%d",&a[i]);
}
k = dp[0] = 1;
for(int i(1);i < n;i++){
int max(-1);
for(int j(0);j < i;j++)
max = a[j]<a[i]&&dp[j]>=max ? dp[j]+1:max;
dp[i] = max == -1?1:max;
k = dp[i] > k ? dp[i]:k;
}
stack<int> s;
for(int i(n-1);i >= 0;i--){
if(k == dp[i]){
s.push(a[i]);
k--;
}
}
while(!s.empty()){
printf("%d ",s.top());
s.pop();
}
return 0;
}
发表于 2020-02-16 14:53:28
回复(2)
问题信息
通过挑战的用户
查看代码-
2023-03-12 10:19:44
-
2023-02-23 17:52:15
-
2023-02-08 15:45:01 -
2023-02-07 15:08:32
-
2023-01-19 16:17:15
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K2座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
