Sum of Continuous Sequences

Question

Given an array A with N elements, I want to find the sum of minimal elements in all possible adjacent subsequences of A. I know that if N is small, we can search for all possible subsequences, but since N is up to 10 ^ 5, which might be the best way to find this amount?

Example: let N = 3 and A [1,2,3], then ans equals 10 as possible continuous subsequences {(1), (2), (3), (1,2), (1,2, 3) , (2,3)}, therefore, the sum of the minimum elements = 1 + 2 + 3 + 1 + 1 + 2 = 10

Answer 1

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

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

• You can precompile L and R for all i in linear time using the stack. Pseudocode:

   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 change the array and run the same algorithm to find R

• How to work with equal elements? Suppose that a[i] is a pair <a[i], i> . Now all the elements are different.

The complexity of the time is O(n) .

Here is the full pseudocode (I assume that int can contain any integer value here, you should choose a valid type to avoid overflow of the real code. I also assume that all elements are different):

 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 

Answer 2

If the list is sorted, you can consider all subsets for size 1, then 2, and then 3, N. The algorithm is initially somewhat inefficient, but the optimized version is lower. Here is some pseudo code.

 let A = {1, 2, 3} let total_sum = 0 for set_size <- 1 to N total_sum += sum(A[1:N-(set_size-1)]) 

First, sets with one element: {{1}, {2}, {3}}: summarize each of the elements.

Then the sets of two elements {{1, 2}, {2, 3}}: summarize each element, but the last.

Then the sets of three elements {{1, 2, 3}}: summarize each element, but the last two.

But this algorithm is inefficient. To optimize to O (n), multiply each i-th element by Ni and add (indexing from zero here). The intuition is that the first element is a minimum of N sets, the second is a minimal set of N-1, etc.

I know this is not a python question, but sometimes the code helps:

 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)