我解决了这个问题，但我不明白它为什么会起作用。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 while i_2 < i_1. 但是谁说条件 a[i_2] < a[i_1] 也会满足？..我不知道如何计算出来......