站外提求助最长上升子序列(方案)
  • 板块题目总版
  • 楼主never_check
  • 当前回复5
  • 已保存回复5
  • 发布时间2023/11/6 19:54
  • 上次更新2023/11/6 21:27:43
查看原帖
站外提求助最长上升子序列(方案)
539861
never_check楼主2023/11/6 19:54

大佬看一下 帮忙改一下 题目 给定一个长为n的序列,求它的最长上升子序列的长度和一种方案。 输入第一行包含一个整数n。 第二行包含n个整数,为给定的序列。 输出的第一行包含一个非负整数,表示最长上升子序列的长度。 第二行包含多个整数,为最长上升子序列中的元素对应的下标 ,按下标从小到大的顺序输出。 输入 5 1 3 2 5 4 输出 3 1 3 4

#include<bits/stdc++.h>
using namespace std;
long long v[1009],dp[1009];
int main(){
	long long n,p,ans=0;
	cin>>n; 
	for(int i=1;i<=n;i++){
		cin>>v[i];
	}
	dp[1]=1;
	for(int i=2;i<=n;i++){
		int len=0;
		for(int j=1;j<i;j++){
			if(v[j]<v[i]){
				if(len<dp[j]){
					len=dp[j];
				}
			}
		}
		dp[i]=len+1;
	}	
	for(int i=1;i<=n;i++){
		if(ans<dp[i]){
			ans=dp[i];
		}
	}
	cout<<ans;

    return 0;
}

2023/11/6 19:54
加载中...