找到分区数组的方法数量

Question

我想要划分一个可能的整数数组的数量，以使数组的左侧部分的最大值大于或等于数组右侧的最大值。

例如， 6 4 1 2 1可以分为：

[[6,4,1,2,1]] [[6][4,1,2,1]] [[6,4][1,2,1]] [[6,4,1][2,1]] [[6,4,1,2][1]] [[6][4,1][2,1]] [[6][4][1,2,1]] [[6][4][1,2][1]] [[6][4,1,2][1]] [[6,4,1][2][1]] [[6][4,1][2][1]] [[6,4][1,2][1]]

总共12种分区方式。

我尝试了一种递归方法，但由于超过时间限制，它失败了终止的终止。另外，这种方法并未始终给出正确的输出。

在另一种方法中，我采用了数组，以减少顺序对其进行排序，然后对于每个元素，我检查天气都位于原始数组的右边，如果确实添加了它的分区，也将其分区为先前的数字。p>我想要一种解决此问题的方法，任何实现或伪代码，或者只是做到这一点的想法。

Answer 1

我设计了一种简单的递归算法。我将尝试通过您的示例解释;

• 首先，检查[6]是否是分区的可能/有效部分。
• 这是一个有效的分区，因为([6](的最大元素比剩余部分([4,1,2,1](最大值大。

• 由于它是有效的分区，因此我们可以使用算法的递归部分。

  concatenate([6],algorithm([4,1,2,1]))
  

• 现在分区

  [[6][4,1,2,1]], [[6][4,1][2,1]], [[6][4,1][2,1]] [[6][4][1,2,1]] [[6][4][1,2][1]] [[6][4,1,2][1]] 
  

  在我们当前的解决方案集中。

• 检查[6,4]是否是分区的可能/有效部分。

• 继续这样直到达到[6,4,1,2,1]。