整数链表中的最长递增子序列

Question

给定一个整数的单向链表，我需要将最长的递增子序列作为新的链表返回。例如，给定的列表是: 1->5->4-> 3->6->8->12 ->10新的列表应该是:3->6->8->12。

我已经尝试遍历列表，并通过

if (n.data < n.next.data)
  newList.add(n);

当列表达到最大长度时，我如何存储节点和计数，然后返回它？感谢前面的内容:)

Answer 1

你应该尝试更多，以获得如何处理问题的想法。这可以通过在纸上/在思考中设计你将如何解决问题来完成。

• 你需要维护一个最大的子列表currentSublist.

，并且

• 一个当前的子列表and

由于可能会添加当前节点，因此应该将其与前一个节点( currentSubList的最后一个元素)进行比较。由于获取单个链表的最后一个元素的开销很大，因此在处理完节点后，我记得该节点为priorNode。

在伪代码中：

List<Integer> maxSublist = new SingleLinkedList<>(); // Empty list.

List<Integer> currentSublist = new SingleLinkedList<>();
Node priorNode = null;
for (Node node = list.head(); node != null; node = node.next) {
     if (priorNode == null || node.data > priorNode.data) {
         currentSublist.add(node);
     } else {
         ...
     }
     if (currentSublist.size() > maxSublist.size()) {
         maxSublist = currentSublist;
     }
     priorNode = node;
}
return maxSublist;

顺便说一句，上面并不是唯一的解决方案。在填写...之后，您可能需要修改代码。

对于下一项任务，试着用这种方式自己找到解决方案。意识到你需要什么:当前的子列表和之前的最大子列表。这是一种困难的难题，当totaLLy自己解决它时，它会带来更多的乐趣。