c++ - 如何找到所有连续子序列的差异？

Question

我需要一个有效的算法，它可以求出所有连续子序列的差之和，但我不知道该怎么做。

例如12345的所有连续子序列:

12    (Dif = 1)
23    (Dif = 1)
34    (Dif = 1)
45    (Dif = 1)
123   (Dif = 2)
234   (Dif = 2)
345   (Dif = 2)
1234  (Dif = 3)
2345  (Dif = 3)
12345 (Dif = 4)

Sum of the difference = 20

序列元素的计数 >= 2 <= 300000。

每个元素 >= 1 <= 10^7。

时限:1s。

我写了代码，但是太慢了:

#include <bits/stdc++.h>

using namespace std;

int main() {
    cin.tie(0);
    iostream::sync_with_stdio(false);

    int count;
    cin >> count;

    int elem;

    vector<int> vec;
    int sum = 0;

    for (int i = 0; i < count; i++) {
        cin >> elem;

        if (vec.size() > 0) {
            sum += abs(vec.back() - elem);
        }

        vec.push_back(elem);
        if (vec.size() > 2) {
            sum += abs(*max_element(vec.begin(), vec.end()) -             *min_element(vec.begin(), vec.end()));
        }

        for (int z = 3; z < count; z++) {
            if (vec.size() > z) {
                sum += abs(*max_element(vec.begin() + i - z + 1, vec.end()) - *min_element(vec.begin() + i - z + 1, vec.end()));
            }
        }
    }

    cout << sum;

    return 0;
}

我发现子序列的个数可以通过三角数公式求出(其中n是序列的长度):

count = 1/2 * n * (n - 1);

对于 n = 300000，子序列的计数为 450 亿。

如何更快地完成？我需要算法。

Answer 1

我的第一个想法是构建一棵树以记住子答案(即动态规划)并将答案组合在一起。然而，每个更高的分支严格来说并不是它下面的节点的总和。考虑例如:

但是，我注意到节点是可预测的。即:

当扩展到 6 个连续节点时:

概括地说就是

SUM( i * (n - i) ) with i = [1 .. n) where n >=2

这当然在 O(N) 时间内运行，除了加 + 乘之外不需要任何其他东西。

---

然而，令我困扰的是，也许这个求和公式可以简化为一个简单的方程式。所以我查找了 properties of summation formulas并努力得到一个简单的方程式:

这意味着 (n^3 - n)/6 应该在 O(1) 时间内执行。我测试了前 6 个，它给出了正确的答案...