algorithm - 打印/返回数组中所有大小为 3 的递增子序列的高效程序

Question

给定一个数组

1, 6, 5, 2, 3, 4

我们需要打印

1 2 3
1 3 4
1 2 4
2 3 4

最好的方法是什么？这是动态规划吗？

有没有比蛮力 O(n3) 更好的方法？我确定有。

我说动态规划的原因是因为我可以将其视为类似的东西

• 对于“1”(打印数组其余部分子序列大小为 2 的子问题的所有结果)。

• 对于“2”(打印数组其余部分子问题的所有结果，子序列大小为 2)

然后继续这样。

但是，上述两个结果有很多重叠，所以我想我们需要找到一种有效的方法来重用它。

好吧，这些只是随意的想法。你可以用正确的方法纠正我。

好的，让我纠正一下，如果不打印，我需要返回不同的递增序列。我的观点是，我需要找到一种方法以最有效的方式获取这些序列。

Answer 1

您可以遍历数组并记住在当前点之前可能存在的部分序列。打印并忘记任何长度达到 3 的序列。

例子:

(1 6 5 2 3 4)
  ^
remember ((1))

(1 6 5 2 3 4)
    ^
remember ((1) (1 6) (6))

(1 6 5 2 3 4)
      ^
remember ((1) (1 6) (6) (1 5) (5))

(1 6 5 2 3 4)
        ^
remember ((1) (1 6) (6) (1 5) (5) (1 2) (2))

(1 6 5 2 3 4)
          ^
remember ((1) (1 6) (6) (1 5) (5) (1 2) (2) (1 3) (1 2 3) (2 3) (3))
print and forget (1 2 3)
remember ((1) (1 6) (6) (1 5) (5) (1 2) (2) (1 3) (2 3) (3))

(1 6 5 2 3 4)
            ^
remember ((1) (1 6) (6) (1 5) (5) (1 2) (2) (1 3) (2 3) (3) (1 4) (1 2 4) (2 4)
          (1 3 4) (2 3 4) (3 4) (4))
print and forget (1 2 4)
print and forget (1 3 4)
print and forget (2 3 4)
done.

挑战似乎在于为内存的子序列选择合适的数据结构。