帮我把下列代码转换为c++：import java.io.*; import java.util.TreeMap; public class Main{ public static void main(String[] args)throws IOException{ BufferedReader read = new BufferedReader(new InputStreamReader(System.in)); int n = Integer.parseInt(read.readLine()); String[] str = read.readLine().split(" "); int dp[] = new int[n];//以array[i]结尾的序列的最长长度 int array[] = new int[n]; for(int i=0;i<n;i++){ array[i] = Integer.parseInt(str[i]); dp[i] = 0; } int max = 0;//最长子序列长度 int flag = 0;//当前最长序列 TreeMap<Integer,Integer> map = new TreeMap<Integer,Integer>();//（长度为i的最小结尾数, 序列长度i) for(int i=0;i<n;i++){ Integer key = map.ceilingKey(array[i]); if(key == null){//没找到ceiling，说明当前array是最大的，添加一个键值对，序列长度加1 map.put(array[i],++flag); dp[i] = flag; }else{//找了，更新，（键1，值1）替换成（键2，值1) dp[i] = map.get(key); map.remove(key); map.put(array[i],dp[i]); } max = Math.max(max, dp[i]); } //System.out.println(max); String sout = ""; for(int j = n-1;j>=0;j--){//倒序遍历，遇到len,len-1,len-1...将其加入字符串 if(dp[j] == max){ sout = array[j]+" "+sout ; max--; } } System.out.print(sout); } }

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#define MAXN 100005
int array[MAXN],dp[MAXN],n;//以array[i]结尾的序列的最长长度
int main(){
scanf("%d",&n);
for(int i=0;i<n;i++){
scanf("%d",&array[i]);
dp[i] = 0;
}
int max = 0;//最长子序列长度
int flag = 0;//当前最长序列
for(int i=0;i<n;i++){
int j=0,k=max;//二分查找
while(j<k){
int mid = (j+k)>>1;
if(dp[mid]<array[i]){
j = mid+1;
}else{
k = mid;
}
}
dp[j] = array[i];
if(j == max){
max++;
flag++;//标记序列长度
}
}
printf("%d\n",flag);
return 0;
}

相关问题

这段代码请帮我翻译成c++语言:import java.io.*; import java.util.TreeMap; public class Main{ public static void main(String[] args)throws IOException{ BufferedReader read = new BufferedReader(new InputStreamReader(System.in)); int n = Integer.parseInt(read.readLine()); String[] str = read.readLine().split(" "); int dp[] = new int[n];//以array[i]结尾的序列的最长长度 int array[] = new int[n]; for(int i=0;i<n;i++){ array[i] = Integer.parseInt(str[i]); dp[i] = 0; } int max = 0;//最长子序列长度 int flag = 0;//当前最长序列 TreeMap<Integer,Integer> map = new TreeMap<Integer,Integer>();//（长度为i的最小结尾数, 序列长度i) for(int i=0;i<n;i++){ Integer key = map.ceilingKey(array[i]); if(key == null){//没找到ceiling，说明当前array是最大的，添加一个键值对，序列长度加1 map.put(array[i],++flag); dp[i] = flag; }else{//找了，更新，（键1，值1）替换成（键2，值1) dp[i] = map.get(key); map.remove(key); map.put(array[i],dp[i]); } max = Math.max(max, dp[i]); } //System.out.println(max); String sout = ""; for(int j = n-1;j>=0;j--){//倒序遍历，遇到len,len-1,len-1...将其加入字符串 if(dp[j] == max){ sout = array[j]+" "+sout ; max--; } } System.out.print(sout); } }

#include<stdio.h>
#include<string.h>
int main(){
int n,i,j,max=0,flag=0,key;
scanf("%d",&n);
int array[n],dp[n];
char str[100];
memset(dp,0,sizeof(dp)); //初始化dp数组
memset(str,0,sizeof(str)); //初始化输入字符串
getchar(); //吸收多余的空格
fgets(str,100,stdin); //读取输入字符串
char * pch;
pch = strtok(str," "); //按照空格分割字符串，取出每个数值
for(i=0;pch!=NULL;i++){
array[i] = atoi(pch); //将字符转化为数字
pch = strtok(NULL," "); //读取下一个数值
}
for(i=0;i<n;i++){
for(j=0;j<i;j++){
if(array[i]>array[j]&&dp[j]>dp[i]){ //发现长度更长的序列
dp[i] = dp[j]; //更新dp值
}
}
dp[i]++; //dp值加1
if(dp[i]>max){ //更新最长序列长度
max = dp[i];
flag = i; //记录最长子序列的尾部位置
}
}
printf("%d\n",max);
char sout[100];
memset(sout,0,sizeof(sout)); //初始化输出字符串
while(max>0){ //从最长子序列尾部往前遍历，构造最长子序列字符串
sprintf(sout+strlen(sout),"%d ",array[flag]);
max--;
flag--;
while(dp[flag]!=max){ //找到长度为max-1的位置（也就是构成最长子序列的上一个位置）
flag--;
}
}
printf("%s",sout);
return 0;
}