algorithm - 连续序列之和

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

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

• 如果我们知道L和 R , 我们应该添加 (i - L) * (R - i) * a[i]到答案。

• 可以预先计算L和 R对于所有 i在线性时间内使用堆栈。伪代码:

  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]是一对<a[i], 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