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

Question

我正在尝试使用代码来打印最长的递增子序列，该代码有效但它没有打印正确的最长递增子序列。

---

例如，如果输入是:3,5,11,8,4,7,1,2,10,12,9,6

输出为:[1, 2, 6, 9, 12]

我想要的输出是:3,4,7,10,12

我已经调试了插入和打印数组列表的方式及其正确的方式，我相信这里有问题，为什么是错误的？为什么它改变了数字的顺序!？

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;
}

Answer 1

您的方法不能起作用。您正在使用一个 列表来收集最长的序列。但是您的输入序列可以有多个递增序列。也许是从索引 0 到 5 的；另一个从索引 10 到 20。

换句话说；你需要一个不同的策略；而“直截了当”的方法是这样的:

1. 迭代输入列表，以“收集”所有递增序列(换句话说:这将是列表的列表)。
2. 之后，您查看该列表列表以找到最大长度的列表

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

但如前所述:第一个天真的实现是简单地识别输入列表中的所有“增加+完整”序列。然后你从那里开始工作。

(因为我认为这是某种家庭作业项目，所以我只提供指导思想，不提供源代码。实现留给读者作为练习)

编辑:解决评论“如何避免记住‘相等’序列”。

假设您的输入是这个序列:1,2,3,0,1,2,3,4,1,2,3当你在那里寻找增加的序列时，你应该找到:

(1, 2, 3) 和 (0, 1, 2, 3, 4), 和 (1, 2, 3)

你是对的:如果你将以上元组表示为 List<Integer> ;那么“正确”的代码将收集三个列表；其中第一个和第三个将相等(因为它们包含完全相同的数字)。

当您将这些列表存储在 List<List<Integer>> 中时那么，是的，您的代码必须考虑重复项。 一种避免这种情况的方法是使用 Set<List<Integer>>相反 - 因为 Set 本质上确保存储在该集合中的所有条目都不相等。换句话说:当您将两个具有相同内容的列表添加到一个 Set 对象时，那么最后，该 Set 将只包含这两个列表中的一个。 (需要注意的一件事 - 当您在此处使用 HashSet 时，add 操作的顺序将丢失)。

最后:而不是使用 Set<List<Integer>>你也可以使用 Map<Integer, Integer> “key”是序列的长度； “值”是输入列表中的第一个索引。

换句话说:与其记住整个序列，您还可以只记住序列从哪个位置开始，以及该序列有多少个元素。

长话短说:有许多不同的方法可以解决这个难题，使用各种数据结构和循环/计数机制。所以，不要停留在第一个可用版本上，而是继续玩下去。