问题描述
给出一个整数数组,在 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 afile 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 theO(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 muchinvolved in mathematical notation to be included on a site without mathjssupport... I will give the sketch of the proof and let the details to thereader (I know it's lame).
解决方案使用多个技巧:
- 所有子数组的最大值之和等于每个
最大值的乘积之和乘以这是最大值的子数组的数量 - 可以将所有子数组的集合划分为一组
子数组。此分区中的每个集合仅包含具有相同
最大元素的子数组,并且集合的大小易于计算
将问题的元素命名为:
- 初始数组称为:
A
。值A [i]
是数组中基于0的索引i
的值。 - 数组的大小为
n
。数组从索引0
扩展到n-1
。
- The initial array is called:
A
. The valueA[i]
is the value at the 0-based indexi
in the array. - The size of the array is
n
. The array extends from index0
ton-1
.
首先,我定义子数组的 leader ,这是索引 i
子数组中元素的
,使得
子数组和子数组中每个元素的值 A [i]
最大值在索引 j< i
有
A [j] 。 (作为练习留出证明)。
I say that equality of leader defines an equivalence relation on thesub-arrays. (proof left as an exercise).
据此,我们知道等价类。另外,等价类中的所有元素的
都具有相同的最大值(由于 leader 函数的定义)。
From this, we know that the equivalence classes form a partition of the set ofall sub-arrays. In addition all elements from an equivalence class have thesame 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 leaderis 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 ofi
whereA[l(i)] >= A[i]
or-1 if no such index existsr(i)
wich is the first index on the right ofi
whereA[l(i)] > A[i]
orn
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 thecomputation is almost the same I will only explain computation of l(i)
. Wemaintain 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 valueis 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 thestack 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 eachelement is
- 已更新一次
- 已被推送一次
由于我们不能多次弹出元素,所以内部的
while
循环不会对于整个阵列扫描,运行
的时间要超过 n
次。
As we cannot pop an element more than once, the inner
while
loop doesn't runmore 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 equivalenceclasses and use this in our summation. Leading to an
O(n)
algorithm, as weneed:
-
O(1)
读取r(i)
-
O(1)
读取l(i)
-
O(1)
读取A(i)
在E_i中子数组的最大值
O(1)
to readr(i)
O(1)
to readl(i)
O(1)
to readA(i)
the maximal value of the sub-arrays inE_i
这篇关于问:所有分段中所有最大值的总和O(N)的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持!