连续序列的和

Question

给定一个有N个元素的数组A，我想在A的所有可能的连续子序列中找到最小元素的总和。我知道如果N很小，我们可以寻找所有可能的子序列，但是当N高达10^5时，找到这个总和的最佳方法是什么？

示例：设 N=3 且 A[1，2，3] 则 ans 为 10，作为可能的连续子序列 {（1），（2），（3），（1，2），（1，2，3），（2，3）} 因此最小元素之和 = 1 2 3 1 1 2 = 10

Answer 1

如果列表被排序，您可以考虑大小为1、2、3到N的所有子集。该算法最初有点低效，但下面是优化版本。这是一些伪代码。

let A = {1, 2, 3}
let total_sum = 0

for set_size <- 1 to N
    total_sum += sum(A[1:N-(set_size-1)])

首先，用一个元素设置:{{1}、{2}、{3}}:对每个元素求和。

然后，两个元素的集合{{1，2}，{2，3}}:对除最后一个元素之外的每个元素求和。

然后，三个元素的集合{{1,2,3}}：将每个元素相加，但最后两个元素相加。

但是这种算法效率很低。要优化到O(n)，将每个第I个元素乘以N-i并求和(此处从零开始索引)。直觉是第一个元素是N个集合的最小值，第二个元素是N-1个集合的最小值，以此类推。

我知道这不是一个python问题，但有时代码会有所帮助:

A = [1, 2, 3]

# This is [3, 2, 1]
scale = range(len(A), 0, -1) 

# Take the element-wise product of the vectors, and sum
sum(a*b for (a,b) in zip(A, scale))

# Or just use the dot product
np.dot(A, scale)

Answer 2

> < li>

让我们修复一个元素(< code>a[i])。我们想知道比位于< code>i(L)左边的元素小的最右边元素的位置。我们还需要知道比位于< code>i(R)右侧的元素小的最左侧元素的位置。

如果我们知道L和R，我们应该在答案中添加（i - L）* （R - i）* a[i]。

可以使用堆栈在线性时间内为所有i预计算L和R。伪代码：

s = new Stack
L = new int[n]
fill(L, -1)
for i <- 0 ... n - 1:
    while !s.isEmpty() && s.top().first > a[i]:
        s.pop()
    if !s.isEmpty():
        L[i] = s.top().second
    s.push(pair(a[i], i))

我们可以反转数组并运行相同的算法来查找R。

如何处理相等元素？让我们假设a[i]是一对

时间复杂度为 O（n）。

这是一个完整的伪代码（我假设int可以在这里保存任何整数值，您应该选择一种可行的类型以避免真实代码中的溢出。我还假设所有元素都是不同的）：

int[] getLeftSmallerElementPositions(int[] a):
    s = new Stack
    L = new int[n]
    fill(L, -1)
    for i <- 0 ... n - 1:
        while !s.isEmpty() && s.top().first > a[i]:
            s.pop()
        if !s.isEmpty():
            L[i] = s.top().second
        s.push(pair(a[i], i))
    return L

int[] getRightSmallerElementPositions(int[] a):
    R = getLeftSmallerElementPositions(reversed(a))
    for i <- 0 ... n - 1:
        R[i] = n - 1 - R[i]
    return reversed(R)

int findSum(int[] a):
    L = getLeftSmallerElementPositions(a)
    R = getRightSmallerElementPositions(a)
    int res = 0
    for i <- 0 ... n - 1:
        res += (i - L[i]) * (R[i] - i) * a[i]
    return res