如何找到最长的递增子序列？

Question

如何找到最长的递增子序列？

4

我正在尝试使用一段代码来打印最长的递增子序列，代码可以运行，但它没有打印出正确的最长递增子序列。

例如，如果输入是：3,5,11,8,4,7,1,2,10,12,9,6，则输出为：[1, 2, 6, 9, 12]，而我想要的输出是：3,4,7,10,12。

我已经调试了插入和打印ArrayList的方法，它是正确的。我相信在这里有什么问题，为什么会出现错误？为什么会改变数字的顺序？请帮我解决问题。

public static ArrayList<Integer> lengthOfsequance(ArrayList<Integer> nums) {

    if (nums == null || nums.size() == 0)
        return null;
    ArrayList<Integer> list = new ArrayList<Integer>();
    for (int num : nums) 
    {
        if (list.size() == 0 || num > list.get(list.size() - 1)) 
            list.add(num);
        else
        {
            int i = 0;
            int j = list.size() - 1;
            while (i < j) 
            {
                int mid = (i + j) / 2;
                if (list.get(mid) < num) 
                    i = mid + 1;
                else
                    j = mid;
            }
           list.set(j, num);
        }
    }
    return list;
}

- reeena11

你的示例中想要什么输出？ - Treycos

2

1、2、6、9、12不是您所输入的3、5、11、8、4、7、1、2、10、12、9、6的子序列。 - JynXXedRabbitFoot

我想要的是3、4、7、10、12，而不是1、2、6、9、12。同时，我不能改变数字的顺序。 - reeena11

哦，我明白了。但是，3、5、8、10、12也是有效的输出吗？ - Treycos

1

我很感激这个惊喜的接受 :-) - GhostCat

显示剩余2条评论

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- GhostCat · Accepted Answer

你的方法行不通。你使用了一个列表来收集最长的序列，但是输入序列可能有多个递增序列。也许从索引0到5有一个，从索引10到20有另一个。

换句话说，你需要一种不同的策略; “直截了当”的方法大致如下：

1.迭代输入列表，以“收集”所有递增序列（换句话说：这将是一个列表的列表）。

2.之后，您查看该List of Lists以找到最大长度。

当然，这可以进一步优化-您不需要记住所有递增序列，您只需要记住之前看到的“最长已完成”序列即可。

但是如上所述：首先，天真的实现是简单地识别输入列表中的所有“递增+完整”序列。然后您从那里开始工作。

（因为我假设这是某种家庭作业项目，所以我只提供指导性思路，而不是源代码。具体实现留给读者练习）

编辑：为了解决评论“如何避免记忆'相等'序列”。

假设您的输入是此序列：1,2,3,0,1,2,3,4,1,2,3 当您在其中寻找递增序列时，应找到：

(1, 2, 3)和(0, 1, 2, 3, 4)，以及(1, 2, 3)

你是对的：如果将上述元组表示为>;然后“正确”的代码将收集三个列表;其中第一和第三个将是相等的（因为它们包含完全相同的数字）。

当您在>>中存储这些列表时，是的，您的代码必须考虑重复项。避免这种情况的一种方法是改用Set> -因为Set自然确保存储在该集合内的所有条目都不相等。

最后，您可以使用Map替换Set>，其中“键”是序列的长度，“值”是输入列表中的“第一个索引”。

换句话说：不必记住整个序列，只需记住序列的起始位置以及该序列包含的元素数量即可。

简而言之：有很多种不同的方法来解决这个难题，可以使用各种数据结构和循环/计数机制。因此，不要停留在第一个可行版本，继续尝试。