本文介绍了问:所有分段中所有最大值的总和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 afile whose path is provided as first argument on the command line.

输入文件的格式应为:


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

  2. 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 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] 。 (作为练习留出证明)。

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 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] 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 read r(i)
  • O(1) to read l(i)
  • O(1) to read A(i) the maximal value of the sub-arrays in E_i

这篇关于问:所有分段中所有最大值的总和O(N)的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持!

08-20 10:33
查看更多