algorithm - 问:所有段中所有最大数的总和O(N)

Question

Closed. This question needs to be more focused. It is not currently accepting answers. Learn more。
想改进这个问题吗更新问题，使其只关注一个问题editing this post
给定整数数组，求O（n）中所有段（区间）中的所有最大数之和。

最佳答案

O（N）溶液
C++源代码如下，程序读取标准输入或
其路径在命令行上作为第一个参数提供的文件。
输入文件的格式应为：
N表示数组中元素数的整数
n个整数，由表示数组元素的空格分隔
编译通过以下方式完成：

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

程序将首先使用 O(n)算法计算和，然后使用
O(n^3)验证算法。
示例运行：

$ ./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的站点上的数学符号中
支持…我会把证据的草图交给
读者（我知道这很蹩脚）。
解决方案使用多种技巧：
所有子数组的max之和等于每个子数组的乘积之和
最大值的子数组的数量，这是最大值
可以将所有子数组的集合划分为一组
子阵这个分区中的每个集合只包含具有相同
极大元和集合的大小很容易计算
让我们命名问题的元素：
初始数组称为： A。值 A[i]是数组中基于0的索引 i处的值。
数组的大小是 n。数组从index 0扩展到 n-1。
首先，我定义了子数组的前导，这是索引 i
在子数组中的一个元素，使得值 A[i]是最大的
子数组和索引 j < i处的子数组中的每个元素都有
A[j]<A[i]直观地说，子数组的前导是其第一个数组的索引
最大值。
我说领导者的平等定义了
子数组。（作为练习留下的证据）。
由此，我们知道
所有子数组。此外，等价类中的所有元素都具有
相同的最大值（由于领导者函数的定义）。
等价类 E_i的大小，其前导的所有子数组的集合
很容易根据以下值计算得出：
i这是 l(i)左侧的第一个索引，其中 i或
-如果不存在这样的索引，则为1
A[l(i)] >= A[i]wich是 r(i)右侧的第一个索引，其中 i或
A[l(i)] > A[i]如果不存在这样的索引
有了这些符号， n的基数是： E_i。作为练习留给读者的证据。
现在是计算值 (i-l(i))*(r(i)-i)和 l(i)的编程技巧。作为
计算几乎是一样的，我只解释 r(i)的计算。我们
使用以下不变量维护索引stak：
堆栈中的索引表示引线
所有指标都在增加
与堆栈中的索引相关联的所有值也按递增顺序排列
我们从左到右扫描阵列。对于每个索引 l(i)我们检查它的值
大于当前堆栈顶部的值。如果是这种情况，则表示其引线位于堆栈顶部的子数组不能超出右侧的当前索引。所以我们将r（栈顶）的值更新为 i我们弹出堆栈的顶部，因为它可能不涉及任何超过 i的子数组。
我们继续更新leaders并弹出堆栈顶部，直到
堆栈为空或 i。然后我们把 A[top of stack] >= A[i]推到堆栈上。
到达数组末尾时，堆栈中可能仍有一些索引。
这意味着它们参与扩展到数组末尾的子数组。
我们将其 i值更新为 r。
整个扫描会更新 N中 r()的所有值。这是因为
元素是
更新一次
推一次
由于不能多次弹出元素，因此内部 O(n)循环不会运行
整个阵列扫描的次数超过 while次。
使用相同的过程计算 n，除了：
我们从右到左向后扫描
我们使用严格的弱比较，因为领导者的定义
我们使用 l()来表示极限是数组的界限
然后我们就可以应用这个公式来计算等价物的大小
在我们的总结中使用这个。导致一个 -1算法，
需要：
O(n)阅读 O(1)
r(i)阅读 O(1)
l(i)读取 O(1)子数组在 A(i)中的最大值

关于algorithm - 问:所有段中所有最大数的总和O(N)，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/46483058/

上一篇：订购产品时找到最佳价格组合的算法

下一篇：algorithm - webgl(和 threejs)中的深度剥离不变性

Answer 1

O（N）溶液
C++源代码如下，程序读取标准输入或
其路径在命令行上作为第一个参数提供的文件。
输入文件的格式应为：
N表示数组中元素数的整数
n个整数，由表示数组元素的空格分隔
编译通过以下方式完成：

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

程序将首先使用 O(n)算法计算和，然后使用
O(n^3)验证算法。
示例运行：

$ ./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的站点上的数学符号中
支持…我会把证据的草图交给
读者（我知道这很蹩脚）。
解决方案使用多种技巧：
所有子数组的max之和等于每个子数组的乘积之和
最大值的子数组的数量，这是最大值
可以将所有子数组的集合划分为一组
子阵这个分区中的每个集合只包含具有相同
极大元和集合的大小很容易计算
让我们命名问题的元素：
初始数组称为： A。值 A[i]是数组中基于0的索引 i处的值。
数组的大小是 n。数组从index 0扩展到 n-1。
首先，我定义了子数组的前导，这是索引 i
在子数组中的一个元素，使得值 A[i]是最大的
子数组和索引 j < i处的子数组中的每个元素都有
A[j]<A[i]直观地说，子数组的前导是其第一个数组的索引
最大值。
我说领导者的平等定义了
子数组。（作为练习留下的证据）。
由此，我们知道
所有子数组。此外，等价类中的所有元素都具有
相同的最大值（由于领导者函数的定义）。
等价类 E_i的大小，其前导的所有子数组的集合
很容易根据以下值计算得出：
i这是 l(i)左侧的第一个索引，其中 i或
-如果不存在这样的索引，则为1
A[l(i)] >= A[i]wich是 r(i)右侧的第一个索引，其中 i或
A[l(i)] > A[i]如果不存在这样的索引
有了这些符号， n的基数是： E_i。作为练习留给读者的证据。
现在是计算值 (i-l(i))*(r(i)-i)和 l(i)的编程技巧。作为
计算几乎是一样的，我只解释 r(i)的计算。我们
使用以下不变量维护索引stak：
堆栈中的索引表示引线
所有指标都在增加
与堆栈中的索引相关联的所有值也按递增顺序排列
我们从左到右扫描阵列。对于每个索引 l(i)我们检查它的值
大于当前堆栈顶部的值。如果是这种情况，则表示其引线位于堆栈顶部的子数组不能超出右侧的当前索引。所以我们将r（栈顶）的值更新为 i我们弹出堆栈的顶部，因为它可能不涉及任何超过 i的子数组。
我们继续更新leaders并弹出堆栈顶部，直到
堆栈为空或 i。然后我们把 A[top of stack] >= A[i]推到堆栈上。
到达数组末尾时，堆栈中可能仍有一些索引。
这意味着它们参与扩展到数组末尾的子数组。
我们将其 i值更新为 r。
整个扫描会更新 N中 r()的所有值。这是因为
元素是
更新一次
推一次
由于不能多次弹出元素，因此内部 O(n)循环不会运行
整个阵列扫描的次数超过 while次。
使用相同的过程计算 n，除了：
我们从右到左向后扫描
我们使用严格的弱比较，因为领导者的定义
我们使用 l()来表示极限是数组的界限
然后我们就可以应用这个公式来计算等价物的大小
在我们的总结中使用这个。导致一个 -1算法，
需要：
O(n)阅读 O(1)
r(i)阅读 O(1)
l(i)读取 O(1)子数组在 A(i)中的最大值