使用特殊规则将数组划分为两个数组

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}。 （现在我们看到为什么不把5加到{1}）。

接下来是4：再次，我们没有选择：{3,5}，{1,2,4}。