高效的程序,用于打印/返回数组中大小为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的子句)

并继续这样下去.

但是,上面两个结果有很多重叠,所以我们需要找到一种有效的重用方法.

嗯,这些只是随意的想法.你可以用正确的appraoch纠正我.

好吧,让我纠正,如果不打印,我需要返回不同的增加序列.我的观点是,我需要找到一种以最有效的方式获得这些序列的方法.

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.

挑战似乎在于为记住的子序列选择适当的数据结构。