Sum of continuous sequences

Question

Given an array A with N elements, I want to find the sum of minimum elements in all the possible contiguous sub-sequences of A. I know if N is small we can look for all possible sub sequences but as N is upto 10^5 what can be best way to find this sum?

Example: Let N=3 and A[1,2,3] then ans is 10 as Possible contiguous sub sequences {(1),(2),(3),(1,2),(1,2,3),(2,3)} so Sum of minimum elements = 1 + 2 + 3 + 1 + 1 + 2 = 10

Answer 1

• Let's fix one element(a[i]). We want to know the position of the rightmost element smaller than this one located to the left from i(L). We also need to know the position of the leftmost element smaller than this one located to the right from i(R).

• If we know L and R, we should add (i - L) * (R - i) * a[i] to the answer.

• It is possible to precompute L and R for all i in linear time using a stack. Pseudo code:

  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))
  

  We can reverse the array and run the same algorithm to find R.

• How to deal with equal elements? Let's assume that a[i] is a pair <a[i], i>. All elements are distinct now.

The time complexity is O(n).

Here is a full pseudo code(I assume that int can hold any integer value here, you should choose a feasible type to avoid an overflow in a real code. I also assume that all elements are distinct):

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