问：所有分段中所有最大值的总和O（N）

编程入门行业动态更新时间:2024-10-27 20:26:44

本文介绍了问：所有分段中所有最大值的总和O（N）的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！问题描述

给出一个整数数组，在 O（n）中找到所有段（区间）中所有最大值的总和。

Given an array of integers, find sum of all maximum numbers in all segments ( intervals ) in O(n).

推荐答案

O（n）中的解决方案

C ++源代码紧随其后，程序读取标准输入或文件

Solution in O(n)

The C++ source code follows, the program reads either the standard input or a file whose path is provided as first argument on the command line.

输入文件的格式应为：

N一个代表数组中元素数量的整数

N个整数，它们之间用空格隔开，代表数组的元素

编译是通过以下方式完成的：

Compilation is done through:

g++ -std=c++14 -g -Wall -O0 solution.cpp -o solution

程序将首先计算使用 O（n）算法求和，然后使用 O（n ^ 3）算法进行验证

The program will first compute the sum using the O(n) algorithm then with the O(n^3) algorithm for verification.

示例运行：

$ ./solution.exe 3 4 5 6 O(n) sum: 32 O(n^3) sum: 32

源代码：

#include <cstdio> #include <algorithm> #include <iomanip> #include <iostream> #include <vector> #include <stack> using namespace std; int main(int argc, char* argv[]) { if(argc > 1) freopen(argv[1], "r", stdin); // load input array int N; cin >> N; vector<int> A(N); for(auto& ai : A) cin >> ai; // compute sum max of all subarrays in O(n) vector<int> l(N); vector<int> r(N); stack<int> s; for(int i=0; i<N; ++i) { while(s.size() && A[s.top()] < A[i]) { r[s.top()] = i; s.pop(); } s.push(i); } while(s.size()) { r[s.top()] = N; s.pop(); } for(int i=N-1; i>=0; --i) { while(s.size() && A[s.top()] <= A[i]) { l[s.top()] = i; s.pop(); } s.push(i); } while(s.size()) { l[s.top()] = -1; s.pop(); } int sum = 0; for(int i=0; i<N; ++i) { int cs = A[i]*(i-l[i])*(r[i]-i); sum += cs; } cout << "O(n) sum: " << sum << '\n'; // compute sum using O(n^3) algorithm for verification sum = 0; for(int i=0; i<N; ++i) { for(int j=i; j<N; ++j) { int cs = *max_element(begin(A)+i, begin(A)+j+1); sum += cs; } } cout << "O(n^3) sum: " << sum << '\n'; }

解决方案的证明

首先，这不是完整的证明。我有一个证明，但是在没有mathjs 支持的网站上包含太多的涉及数学符号...我将给出证明的草图，并将详细信息交给读者（我知道这很la脚）。

Proof of the solution

First, this is not the complete the proof. I have a proof but it is too much involved in mathematical notation to be included on a site without mathjs support... I will give the sketch of the proof and let the details to the reader (I know it's lame).

解决方案使用多个技巧：

所有子数组的最大值之和等于每个最大值的乘积之和乘以这是最大值的子数组的数量
可以将所有子数组的集合划分为一组子数组。此分区中的每个集合仅包含具有相同最大元素的子数组，并且集合的大小易于计算

将问题的元素命名为：

初始数组称为： A 。值 A [i] 是数组中基于0的索引 i 的值。
数组的大小为 n 。数组从索引 0 扩展到 n-1 。

The initial array is called: A. The value A[i] is the value at the 0-based index i in the array.
The size of the array is n. The array extends from index 0 to n-1.

首先，我定义子数组的 leader ，这是索引 i 子数组中元素的，使得子数组和子数组中每个元素的值 A [i] 最大值在索引 j< i 有 A [j] 。直观地讲，子数组的 leader 是其第一个最大值的索引。

First, I define what I call the leader of a sub-array, this is the index i of an element in the subarray such that the value A[i] is maximal for the sub-array and every elements in the sub-array at an index j < i have A[j]<A[i]. Intuitively, the leader of a sub-array is the index of its first maximal value.

我说 leader 在子数组上定义了等效关系。（作为练习留出证明）。

I say that equality of leader defines an equivalence relation on the sub-arrays. (proof left as an exercise).

据此，我们知道等价类形成组所有子数组的分区。另外，等价类中的所有元素的都具有相同的最大值（由于 leader 函数的定义）。

From this, we know that the equivalence classes form a partition of the set of all sub-arrays. In addition all elements from an equivalence class have the same maximal value (due to the definition of the leader function).

等价类 E_i 的大小，所有子数组的 leader 为 i ，可以很容易地从以下值计算得出：

The size of an equivalence class E_i, the set of all sub-arrays whose leader is i, is easily computed from the values:

l（i）是 i 左侧的第一个索引，其中 A [l（i）]> = A [i] 或 -1（如果不存在这样的索引）
r（i）是第一个索引 i 的权利，其中 A [l（i）]> A [i] 或 n （如果不存在这样的索引）

l(i) which is the first index on the left of i where A[l(i)] >= A[i] or -1 if no such index exists
r(i) wich is the first index on the right of i where A[l(i)] > A[i] or n if no such index exists

使用这些符号， E_i 的基数为：（il（i））*（r（i）-i ）。留给读者练习的证明。

With these notations the cardinal of E_i is: (i-l(i))*(r(i)-i). Proof left as an exercise to the reader.

现在是编程技巧，可以计算值 l（i）和 r（i）。由于的计算几乎相同，因此我只解释 l（i）的计算。我们保持索引的稀疏性，具有以下不变式：

Now the programming trick to compute the values l(i) and r(i). As the computation is almost the same I will only explain computation of l(i). We maintain a stak of indexes, with the following invariants:

堆栈中的索引表示 leaders
所有索引都按升序排列
与堆栈中索引相关的所有值也都按升序排列

我们从左到右扫描阵列。对于每个索引 i ，我们检查其值是否大于栈顶的当前值。如果是这种情况，则意味着其 leader 是堆栈顶部的子数组不能超出右侧的当前索引。因此，我们将 r（堆栈顶部）的值更新为 i 。我们弹出堆栈的顶部，因为它可能不参与任何超出 i 的子数组。我们继续更新 leaders 并弹出堆栈顶部，直到堆栈为空或 A [堆栈顶部]> = A [i] 。然后我们将 i 压入堆栈。到达数组末尾时，堆栈中仍可能有一些索引。这意味着他们参与了扩展到数组末尾的子数组。我们将其 r 的值更新为 N 。

We scan from left to right the array. For each index i we check if its value is greater than that of the current top of the stack. If this is the case it means the sub-array whose leader is the top of the stack cannot extend past the current index on the right. So we update the value of r(top of stack) to be i. We pop the top of the stack as it may not be involved in any sub-array extending past i. We continue to update leaders and pop the top of the stack until either the stack is empty or A[top of stack] >= A[i]. Then we push i on the stack. When reaching the end of the array there may still be some indexes in the stack. This means they participate in sub-arrays extending to the end of the array. We update their r value to be N.

整个扫描将更新 O（n）中 r（）的所有值。这是因为每个元素

The whole scan updates all values for r() in O(n). This is because each element is

已更新一次
已被推送一次

由于我们不能多次弹出元素，所以内部的 while 循环不会对于整个阵列扫描，运行的时间要超过 n 次。

As we cannot pop an element more than once, the inner while loop doesn't run more than n times for the whole array scan.

相同的过程用于计算 l（）除外，

Same process is used to compute l() except that:

我们从右向左扫描
我们使用严格的弱比较，因为定义了 leader
我们使用 -1 表示限制是数组的边界

we scan backward from right to left
we use a strict weak comparison because of the definition of leader
we use -1 to indicate the limit is the bound of the array

然后我们可以应用公式来计算等价的类，并在我们的求和中使用。导致 O（n）算法，因为我们需要：

Then we can just apply the formula to compute the size of the equivalence classes and use this in our summation. Leading to an O(n) algorithm, as we need: