c++ - 使用特殊规则将一个数组分成两个数组

Question

我一直在做练习，偶然发现了一个问题。

给定一个整数数组，确定它是否可以分成两个数组，每个数组都按升序排列。例如 3,1,5,2,4 可以，但 4,8,1,5,3 不可以。

问题就在这里。我不明白为什么第一个数组可以但第二个数组不能。
有提示:
如果我们成功划分了数组的初始段，则其中一部分必须包含到目前为止看到的最大元素。另一部分的最大元素尽可能小显然符合我们的最大利益。因此，给定下一个元素，如果它是此时的最大值，则将其添加到“最大包含部分”。如果不是，则别无选择，只能在可能的情况下将其添加到另一部分(例如:如果它大于该部分的最大元素，但不是当前最大值)。如果此过程失败，则无法进行分区，如果成功，则我们已经演示了分区。

最重要的部分是理解这个分区的逻辑。
提前谢谢你。

Answer 1

让我们在 {3,1,5,2,4} 上使用给定的算法。

第一个数字是 3。我们的分区是 {3}，{}。

接下来是 1。我们无法将其添加到 {3}，因此我们将其添加到另一个:{3}，{1}。

接下来是 5。我们将它添加到 {3}，以便为较小的数字保存 {1}:{3,5}，{1}。

接下来是 2。我们必须将它添加到 {1}:{3,5},{1,2}。 (现在我们明白了为什么不给 {1} 添加 5 是好的。)

接下来是 4:同样，我们别无选择:{3,5},{1,2,4}。