滴滴2023后端 序列拆分

#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_set>
using namespace std;

int auxFunc(vector<int> res, vector<int>nums,vector<int> maxLen,int end)
{
    unordered_set<int>unmap;
    for (int i = end, j = res.size(); j > 0; --i)
    {
        if (maxLen[i] == j)
        {
            // 表示在 arr[i] 这个位置的最大长度为 j 也就是说 这个位置的值应该是 arr[i]
            res[--j] = nums[i];
        }
    }

    // 此时res中就是最终的递增子序列
    for (int i = 0; i < res.size(); i++)
    {
        unmap.insert(res[i]);
    }
    int i = 0;
    while (i < nums.size())
    {
        if (unmap.find(nums[i]) != unmap.end())
        {
            i++;
        }
        else
        { 
            break;
        }
    }
    int temp = nums[i];
    i++;
    for (; i < nums.size(); i++)
    {
        // 不再
        if (unmap.find(nums[i]) == unmap.end() && nums[i] < temp)
        {
            temp = nums[i];
        }
        if (unmap.find(nums[i]) != unmap.end())
        {
            continue;
        }
        if(unmap.find(nums[i]) == unmap.end() && nums[i] > temp)
        {
            return 0;
        }
    }
    return 1;
}

int main()
{
	int n;
	cin >> n;
	while (n--)
	{
		int m;
		cin >> m;
			
		vector<int> nums;
		for (int i = 0; i < m; i++)
		{
			int num;
			cin >> num;
			nums.push_back(num);
		}
		// 找到数组中的单调递增序列
		vector<int>maxLen;
		vector<int>res; // res[i]表示在 i 处

        res.emplace_back(nums[0]);
        maxLen.emplace_back(1);
        for (int i = 1; i < m; i++)
        {
            if (nums[i] > res.back())
            {
                res.emplace_back(nums[i]);
                maxLen.emplace_back(res.size());
            }
            else
            {
                int pos = lower_bound(res.begin(), res.end(), nums[i]) - res.begin();
                res[pos] = nums[i];
                maxLen.emplace_back(pos + 1);
            }
            // 计算出
            int t = auxFunc(res, nums, maxLen,i);
            if (t == 1)
            {
                cout << "Yes" << endl;
                break;
            }
            if (i == m - 1)
            {
                cout << "No" << endl;
            }
        }
	}
}