Untitled

mail@pastecode.io avatar
unknown
c_cpp
7 months ago
1.1 kB
3
Indexable
Never
vector<int> find_longest_increasing_subsequence(vector<int> nums) {
    if (nums.empty()) {
        return {};
    }

    vector<int> lengths(nums.size(), 1);
    int maxLength = 1;
    int maxIndex = 0;

    for (int i = 1; i < nums.size(); ++i) {
        for (int j = 0; j < i; ++j) {
            if (nums[j] < nums[i] && lengths[j] + 1 > lengths[i]) {
                lengths[i] = lengths[j] + 1;
            }
        }

        if (lengths[i] > maxLength) {
            maxLength = lengths[i];
            maxIndex = i;
        }
    }

    vector<int> subsequence;
    int currentIndex = maxIndex;
    subsequence.push_back(nums[currentIndex]);

    while (lengths[currentIndex] > 1) {
        for (int j = currentIndex - 1; j >= 0; --j) {
            if (lengths[j] == lengths[currentIndex] - 1 && nums[j] < nums[currentIndex]) {
                currentIndex = j;
                subsequence.push_back(nums[currentIndex]);
                break;
            }
        }
    }

    reverse(subsequence.begin(), subsequence.end());
    return subsequence;
}