UVa 10134：越大越聪明吗？ （动态规划和最长递增子序列）

Question

private void findLDS() {
    Integer[] array = Arrays.copyOf(elephants.iq, elephants.iq.length);
    Hashtable<Integer, Integer> eq = elephants.elephantiqs;

    Integer[] lds = new Integer[array.length];
    Integer[] prev= new Integer[array.length];
    lds[0] = 0;
    prev[0] = 0;

    int maxlds = 1, ending=0;

    for(int i = 0; i < array.length; ++i) {
        lds[i] = 1;
        prev[i] = -1;

        for (int j = i; j >= 0; --j) {
            if(lds[j] + 1 > lds[i] && array[j] > array[i] && eq.get(array[j]) < eq.get(array[i])) {
                lds[i] = lds[j]+1;
                prev[i] = j;
            }
        }
        if(lds[i] > maxlds) {
            ending = i;
            maxlds = lds[i];
        }
    }
    System.out.println(maxlds);
    for(int i = ending; i >= 0; --i) {
        if(prev[i] != -1) {
            System.out.println(eq.get(array[prev[i]])); 
        }

    }

我将此算法基于这个SO问题。该代码试图找到最长的递减子序列而不是递增子序列。 array[] 按降序排序，我还有一个哈希表，其中大象的智商作为其权重的键。

我很难正确理解 DP，我需要一些帮助。

除了跟踪 prev[] 中所选的序列（它总是丢失一个元素）之外，我的算法似乎工作得很好。有谁知道该怎么做？

Answer 1

解决这个问题的几种方法：

1. 按权重降序排序，然后找到最长的递增子序列。
2. 按 IQ 降序排序，然后找到权重的最长递增子序列。
3. 和4.只是（1）和（2），交换单词“增加”和“减少”

如果你不理解最长增加子序列O(N^2)的DP，它基本上是这样的：

1. 因为列表有无论如何，要严格增加/减少，您可以预先消除一些大象以使集合独一无二。
2. 创建一个数组，我将其称为llis，代表“最长递增子序列”，长度为N，即现在大象的数量。创建另一个名为 last 且长度相同的数组。我假设大象的排序列表称为数组，就像您的问题陈述中一样。
3. 假设您已经按降序对大象进行了排序，您将需要找到最长的智商递增子序列。
4. 告诉自己数组 llis 中索引 n 的元素（这是一个不同的“n”）< N 将是 array 子数组从索引 0 到 n（含）的最长递增子序列的长度。还可以说 next 数组中索引 n 处的元素将是 array 中最长递增子序列的下一个索引。
5. 因此，要找到 0 到 N - 1（包括整个数组）的“子数组”中最长递增子序列的长度，只需要找到 N - DP 计算后数组 llis 中的第 1 元素，查找实际子序列将简化为遵循 next 数组中的索引。
6. 现在您知道了要查找的内容，就可以继续使用该算法了。在数组中的索引n处，你如何知道最长的递增子序列是什么？好吧，如果您已经计算了每个 k < 的最长递增子序列的长度以及子序列中的最后一个值。 n，如果大象的智商n，您可以尝试将索引n处的大象添加到以k结尾的最长递增子序列中 比 k 大象的智商还要高。在这种情况下，以大象 n 结尾的最长递增子序列的长度将为 llis[k] + 1。 （另外，请记住将 next[k] 设置为 n，因为递增子序列中的下一个大象将是 n 处的大象。 )
7. 我们找到了 DP 关系 llis[n] = max(llis[n], llis[k] + 1)，在遍历了所有 k 后，严格之前n。只需以正确的顺序（线性）处理 n ，您就应该得到正确的结果。
8. 过程/警告： 1) 按从 0 到 N - 1 的顺序处理 n。 2) 对于每个n，按从n - 1到0的顺序处理k，因为您希望最小化k > 你选择的。 3) 处理完成后，请务必找到数组 llis 中的最大数字以获得最终结果。
9. 由于这被标记为家庭作业，我不会明确说明如何修改它以找到最长递减子序列，但我希望我的解释有助于您对 DP 的理解。如果您选择使用它，您自己应该很容易找出递减版本。 （请注意，可以使用递增版本来解决此问题，如方法 1 或 2 中所述。）