algorithm - 查找长度为 3 的递增(或递减)子序列数？

Question

给定一个正整数数组，我如何找到长度为 3 的递增(或递减)子序列的数量？例如。 [1,6,3,7,5,2,9,4,8​​] 有 24 个，例如 [3,4,8] 和 [6,7,9]。

我找到了长度 k 的解决方案，但我相信这些解决方案可以变得更有效率，因为我们只考虑 k = 3。

例如，一个简单的O(n^3) 解决方案可以通过遍历元素并计算左边有多少元素较少，右边有多少元素较高，可以更快，然后将这两个计数相乘，并将其相加。这是 O(n^2)，显然不能轻易转换为 k > 3。

Answer 1

解决方案可以通过遍历元素，在每个元素上，您可以计算它们左边有多少个元素，更少地使用在 O(log(n)) 中工作的线段树算法，并且通过这种方式，您可以计算出它们右边和更高处有多少个元素，然后将这两个计数相乘，并将其添加到总和中。这是 O(n*log(n))。

您可以在此处了解有关线段树算法的更多信息: Segment Tree Tutorial