Решил задачу и не понимаю почему работает. Задача на нахождение наибольшей возрастающей подпоследовательности C++

Задачка:

Даны N целых чисел X1, X2, ..., XN. Требуется вычеркнуть из них минимальное количество чисел так, чтобы оставшиеся шли в порядке возрастания.

Входные данные Первая строка входного файла INPUT.TXT содержит натуральное число N. Во второй строке записаны N чисел, разделенные пробелом. (N ≤ 10 000, 1 ≤ Xi ≤ 60 000)

Выходные данные В первой строке выходного файла OUTPUT.TXT выведите количество невычеркнутых чисел, во второй – сами невычеркнутые числа через пробел в исходном порядке. Если вариантов несколько, следует вывести любой.

Вот мое решение:

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

int main()
{
    int n;
    cin >> n;
    vector<int> a(n), dp(n, 1);
    for (auto& x : a)
        cin >> x;
    int ans = 1;
    for (size_t i = 1; i < n; i++)
    {
        for (int j = i - 1; j >= 0; --j)
        {
            if (a[j] < a[i])
            {
                dp[i] = max(dp[i], dp[j] + 1);
                ans = max(ans, dp[i]);
            }
        }
    }
    vector<int> arr;
    for (int i = n - 1; i >= 0; i--)
    {
        if (dp[i] == ans && (arr.empty() || a[i] < arr.back()))
        {
            arr.push_back(a[i]);
            --ans;
            if (ans == 0)
                break;
        }
    }
    reverse(arr.begin(), arr.end()); //можно было и без этого, ну да ладно.
    cout << arr.size() << endl;
    for (auto& x : arr)
        cout << x << ' ';
}

Естественно с помощью динамики мы получим ответ о самой длинной возрастающей подпоследовательности. После того как мы посчитали динамику сразу встает вопрос, а как по ней восстановить эту подпоследовательность. Я решил пойти "жадным" путем и начал просто с конца массива dp брать нужные элементы. И честно говоря я не понимаю почему это сработало. А что было бы если я взял какой то элемент из dp[i] = x, а потом для каких-то j < i у меня не нашлось бы dp[j] = (x - 1). Почему все таки всегда найдется?

На самом деле может показаться, что dp[j] - 1 = dp[i] может всегда найтись (ну как бы логично, если есть допустим dp[i_1] = 4, то обязательно должен быть dp[i_2] = 3 при этом i_2 < i_1. Но а кто сказал что условие a[i_2] < a[i_1] тоже будет выполняться?.. Я не знаю как в этом разобраться...