求大佬帮忙解决codeforces 中的Two sequences，为什么我这样过不了

Question

题目链接

Problem - A - Codeforces

下面是我写的，只过了16个测试集。。。

#include<iostream>
#include<vector>
#include<cmath> 
using namespace std;

long long n;
long long nums[500050];
vector<long long> sub1;
vector<long long> sub2;
long long ans = -1;

void dfs(int t){
    if(t == n){
        long long temp1 = sub1.size();
        long long temp2 = sub2.size();
        //cout << temp1 << " " << temp2 << endl;
         if(sub1.size() + sub2.size() == n && abs(temp1-temp2) > ans){
            
            ans = abs(sub1.size()-sub2.size());
            
        }
    }else{
        if(sub1.size() == 0 || sub1[sub1.size()-1] < nums[t]){
            sub1.push_back(nums[t]);
            dfs(t+1);
            sub1.pop_back();
        } 
        if(sub2.size() == 0 || sub2[sub2.size()-1] < nums[t]){
            sub2.push_back(nums[t]);
            dfs(t+1);
            sub2.pop_back();
        }
    }
}

int main(){
    
    
    cin >> n;
    
    for(int i = 0;i<n;i++){
        cin >> nums[i];
    }
    
    dfs(0);
    cout << ans;
    return 0;
} 

Answer 1

您好，麻烦下次问问题的时候把题目一起粘过来，你给的网站我去过了，这里我先把题目放出来，然后再给你解答一下。

题目要求将给定的排列p分成两个不相交的递增子序列，使得这两个子序列的大小之间的差异最大。如果无法满足要求，则输出-1。

你的代码我没看，这里为了简单，我直接用Python给你写一个参考案例吧，你自己可以对应的转为C语言。

def max_difference(n, p):
    # 计算每个元素在排列中的位置
    positions = [0] * (n + 1)
    for i in range(n):
        positions[p[i]] = i
    
    # 定义两个变量记录两个子序列的最大值
    max_left = 0
    max_right = 0
    
    # 遍历排列，根据元素在排列中的位置更新最大值
    for i in range(n):
        if positions[p[i]] > max_left:
            max_left = positions[p[i]]
        else:
            max_right = positions[p[i]]
    
    # 判断是否能够将排列分成两个不相交的递增子序列
    if max_left == 0 or max_right == 0:
        return -1
    
    # 计算两个子序列的大小之间的差异
    difference = abs(max_right - max_left) + 1
    
    return difference

# 输入排列的长度和排列本身
n = int(input())
p = list(map(int, input().split()))

# 调用函数计算最大差异
result = max_difference(n, p)

# 输出结果
print(result)