akshit.lite's blog

Sum Of Maximum's of all contigous sub-arrays of length k of a given Array.
By akshit.lite, history, 9 years ago, In English

I have been thinking of an algorithm which could find the Sum Of Maximum's of all contigous sub-arrays of length k of a given Array. for each k from 1 to n , seperatly. n is the length of the array. I am able to figure out an O(N^2) solution. But could not reduce the complexity further. It would be helpful if someone could tell a sub-quadratic approach.(Possibly O(n) ). This is in reference to this problem. Any help is appreciated. NOTE : the answer for each k has to be printed seperately. Thanks :)

  • Vote: I like it
  • +5
  • Vote: I do not like it

Comments Comments (15)
| Write comment?
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by akshit.lite (previous revision, new revision, compare).

→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by akshit.lite (previous revision, new revision, compare).

→ Reply
»
9 years ago, # |
← Rev. 4   Vote: I like it +1 Vote: I do not like it

Sorry, misunderstood the problem statement.

→ Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Lets focus on each element of the array. For a fixed element, we wonder how many times it will be added to our total sum. Clearly, for every subarray that includes this element as the maximum, we will add it. Let our fixed element be A[x]. Then if i is the last index on the left of x such that A[i] < A[x], and j is the last index on the right of x such that A[j] < A[x], then A[x] will be added exactly (x-i+1)(j-x+1) times(you can use combinatorics to prove this). Note that if we have A[i]=A[x] or A[j]=A[x], we can count this subarray as well, but will have to subtract out some numbers at the end because we overcounted(you can use a map to store counts of each number, then do some combinatorics).

Now the only question is, how do we calculate i and j? Let's generate j first. Iterate through the array from left to right and keep track of a multiset of elements we have seen so far. When we encounter an element, let's remove all smaller elements possible from the multiset and set their j values to be this index. Then add this element to the multiset and move on. We can do a similar thing traversing the array right to left to compute the i values.

Since we iterate and use multiset for deletion, our complexity ends up being O(N log N).

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    We need to find the answer of k=1,k=2 .. k=n seperately. As far as I have understood you are finding sum of all the answers for each k.

    → Reply
»
9 years ago, # |
  Vote: I like it +1 Vote: I do not like it

I solved this problem using fenwick tree. If r[n] is the result, you can figure out for each number in input array which indexes of r it affects. Each number in input array will form a pattern which can be easily processed and queried by fenwick tree.

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    What exactly are you storing in fenwick tree and on which parameter are you processing and querying it ? Can you please elaborate ? (facing problem since I have used only segTree most of the times)

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      Each number in the input array will add to some indexes of r[] in a certain way. You can see that from given example in the question or generate input of your own to see. There is nothing more to the problem than that. After that you can use any interval query/process data structure.

      → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        Won't the worst case complexity of your program be 0(n*n*log(n)) as you have to update the number of times the xth element a[x] be added into r[1] , r[2] , r[3] ... r[k] , where k is the maximum size of the segment where a[x] is maximum. ? It would'nt be a constant value for all k's of a paritcular a[x], right ?

        → Reply
        • »
          »
          »
          »
          »
          9 years ago, # ^ |
            Vote: I like it +1 Vote: I do not like it

          No. What you are describing is of-course of the order O(n^2*(log(n)), But the essence of finding the pattern to be added to the result (by result i don't mean any particular r[i] but the whole result array), is that you can update array r for any a[x] in log(n) time.

          → Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

can it can be solved in nlogn by binary search by first taking cumilative sum??

→ Reply
»
9 years ago, # |
  Vote: I like it +7 Vote: I do not like it

It can be solved in O(n):

http://pastebin.com/xeUpgjTe

For each i = 1, 2, ..., n we can find maximal p < i and minimal q > i such that a[p] >= a[i], a[q] > a[i] or p = 0 or q = n+1 (on left we have >= and on right > to not count twice the same interval). Then, if we fixed i we can observe that, for intervals of length 1, 2, 3, ... min(i-p, q-i)-1 we add to result a[i]*interval_length, for intervals of length min(i-p, q-i), ..., max(i-p, q-i)-1 we add min(i-p, q-i)*a[i] and for intervals of length max(i-p, q-i), ..., q-p-1 we add (q-p-interval_length)*a[i]. We want to have O(n) complexity, so in first case (when intervals have length < min(i-p, q-i)) we can add a[i] to some variable (in my code ,,sum"), and add a[i] to tab[min(i-p, q-i)], then when we will count answer for intervals of length i we will subtract tab[i] from sum and next add to result sum*i. Similar things we can do in second and third case.

→ Reply