UVa _11456 _ Trainsorting

 #include <iostream>

#include <vector>

using namespace std;

int findLongestSymmetricSubsequence(int sequenceLength) {

    // Create mirrored train sequence

    vector<int> symmetricSequence(sequenceLength * 2);

    // Track length of increasing subsequence for each position

    vector<int> subsequenceLengths(sequenceLength * 2, 1);

    int maxSubsequenceLength = 0;

    // Read and mirror the sequence

    for (int i = 0; i < sequenceLength; ++i) {

        int trainCarValue;

        cin >> trainCarValue;

        symmetricSequence[sequenceLength + i] = symmetricSequence[sequenceLength - i - 1] = trainCarValue;

    }

    // Find longest increasing subsequence

    for (int currentIndex = 0; currentIndex < sequenceLength * 2; ++currentIndex) {

        for (int prevIndex = 0; prevIndex < currentIndex; ++prevIndex) {

            // If current element is larger than previous, update subsequence length

            if (symmetricSequence[currentIndex] > symmetricSequence[prevIndex]) {

                subsequenceLengths[currentIndex] = max(

                    subsequenceLengths[currentIndex], 

                    subsequenceLengths[prevIndex] + 1

                );

            }

            // Track maximum subsequence length

            maxSubsequenceLength = max(maxSubsequenceLength, subsequenceLengths[currentIndex]);

        }

    }

    return maxSubsequenceLength;

}

int main() {

    // Optimize input/output performance

    ios::sync_with_stdio(false);

    cin.tie(nullptr);

    cout.tie(nullptr);

    int numberOfTestCases;

    cin >> numberOfTestCases;

    // Process each test case

    while (numberOfTestCases--) {

        int trainLength;

        cin >> trainLength;

        // Solve and output result for current test case

        cout << findLongestSymmetricSubsequence(trainLength) << "\n";

    }

    return 0;

}