判断数组能否划分为两个严格递增子序列的算法优化求助

Hey there! Let's figure out why your code is timing out and fix it up properly.

What's Wrong with the Original Code? #

Your code works for most test cases, but the last one times out due to a few critical issues:

1. String concatenation bottleneck: Using stra += to_string(arr[i]) and similar operations is extremely slow for large arrays. Each concatenation creates a new string, leading to an overall time complexity of O(n²) — this is the main reason for the timeout.
2. Logical bugs:
   • You used >= instead of > for strict increment checks, which violates the problem's requirement of strictly increasing subsequences.
   • The arr[i] != arr[i-1] check causes an out-of-bounds error when i=0 (accessing arr[-1]).
   • The MAX2 != MAX condition is unnecessary and can incorrectly reject valid cases.
3. Unnecessary computations: Building the total string to compare lengths is a waste of time and memory — you don't need to track the entire subsequence, just their last elements.

Optimized Solution #

We can solve this problem in O(n) time and O(1) extra space (excluding the input array) using a greedy approach. The key insight is to only track the last element of each of the two subsequences, rather than storing the entire sequences.

Here's the fixed code:

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

bool run() {
    int numbers;
    cin >> numbers;
    vector<int> arr(numbers);
    for (int i = 0; i < numbers; ++i) {
        cin >> arr[i];
    }

    int last1 = INT_MIN; // Last element of first subsequence
    int last2 = INT_MIN; // Last element of second subsequence

    for (int x : arr) {
        if (x > last1) {
            // Add to first subsequence
            last1 = x;
        } else if (x > last2) {
            // Add to second subsequence
            last2 = x;
        } else {
            // Can't add to either subsequence — invalid case
            return false;
        }
    }

    return true;
}

int main() {
    // Speed up input/output to avoid timeout with large test cases
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int test;
    cin >> test;
    while (test--) {
        cout << (run() ? "Yes\n" : "No\n");
    }

    return 0;
}

Key Optimizations Explained #

1. Greedy tracking of subsequence ends: We only keep track of the last element of each subsequence. For every element:
   • If it's larger than the last element of the first subsequence, append it there.
   • If not, try appending it to the second subsequence.
   • If neither is possible, the array can't be split into two strictly increasing subsequences.
2. Input/output acceleration: The lines ios::sync_with_stdio(false); and cin.tie(nullptr); disable synchronization between C and C++ I/O streams and unlink cin from cout, which drastically speeds up input and output operations — critical for handling large test cases without timing out.
3. Safe array handling: Using vector<int> instead of new int[] avoids memory leaks and simplifies array management.
4. Removed unnecessary operations: No more string concatenation or length comparisons — we focus solely on the logic needed to validate the split.

Testing the Solution #

Let's verify with your sample input:

• For 3 1 5 2 4: We build subsequences [3,5] and [1,2,4] → returns Yes.
• For 4 8 1 5 3: The final element 3 can't be added to either subsequence (last elements are 8 and 5) → returns No.

This code will handle all test cases efficiently, including large ones that caused your original code to time out.

内容的提问来源于stack exchange，提问作者Rupert