java - 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 question算法。此代码试图找到最长的递减子序列，而不是递增。 array []是按降序排列的，我还有一个哈希表，其中大象智商是其权重的键。

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

除了在prev []中跟踪选定的序列（总是错过一个元素）之外，我的算法似乎还不错。有谁知道如何做到这一点？

Answer 1

解决此问题的几种方法：


按权重降序排序，然后找到最长的递增子序列。
按IQ降序排序，然后找到权重最长的递增子序列。
和4.只是（1）和（2），将单词“ increating”和“ decreasing”切换


如果您不了解DP的最长递增子序列O（N ^ 2），则基本上是这样的：


由于无论如何该列表都必须严格增加/减少，因此您可以预先消除一些大象以使该集合唯一。
创建一个数组，我将其称为llis，表示“最长递增子序列”，其长度为N，即现在的大象数量。创建另一个名为last的具有相同长度的数组。我将假设大象排序列表在您的问题陈述中称为array。
假设您已经按照降序对大象进行了排序，那么您将希望找到智商增长时间最长的子序列。
告诉自己，索引 中数组 llis中的元素（这是一个不同的“ n”） array子数组中从索引0到n的最长递增子序列的长度，包括端值。还要说，在索引n中的 next数组中的元素将是最长递增子序列中 array中的下一个索引。
因此，要找到“子数组”中最长的递增子序列的长度（包括0到N-1）（也是整个数组），只需在数组 llis中找到第N-1个元素在DP计算之后，找到实际的子序列将简化为遵循 next数组中的索引。
现在，您知道要查找的内容，可以继续进行算法了。在数组的索引n处，您如何知道最长的递增子序列是什么？好吧，如果您已经计算出每个k llis[k] + 1。 （此外，请记住将 next[k]设置为n，因为递增子序列中的下一个大象将是n处的大象。）
经过严格地位于n之前的所有k s之后，我们发现DP关系为 llis[n] = max(llis[n], llis[k] + 1)。只需以正确的顺序（线性地）处理n s，您应该得到正确的结果。
过程/警告：1）按从0到N-1的顺序处理n。2）对于每个n，按从n-1到0的顺序处理k，因为您要最小化所选的k。 3）完成处理后，请确保在数组 llis中找到最大值，以得到最终结果。
由于这被标记为作业，因此，我不会明确地说出如何修改它以找到最长的递减子序列，但是希望我的解释对您对DP的理解有所帮助。如果您选择使用降级版本，则应该很容易自行确定。 （请注意，可以使用递增版本来解决此问题，如方法1或2中所述。）