I can think of two ways 
Let the array of elements be A, and its size N

We can count sub arrays, based on the sub array's starting index 
For every sub array A[i, j], for its max element to be k, all elements A[p]<=k, i<=p<=j and atleast one element shoud be k, so let us calculate two values i1 and i2 for each index i, such that i1,i2 >= i and
i1 = least value not less than i, such that A[i1]=k, and
i2 = least value not less than i, such that A[i2]>k
clearly every for subarray A[i, j] starting at index i, j < i2 and j >=i1 is the necessary and sufficient condition
hence the no of subarrays starting at index i with max=k are i2i1, and we can calculate these values i1, i2 for all i in O(N) by traversing the array from right to left.

We can solve it by divide and conquer approach, in which we divide the array into two equal parts , count no of subarrays for which max=k in each of the two parts and combine those two to also count the no of subarrays which have max=k and their start index in the first part and end index in the second part.
To do that for each slice of array A[i,j] we calculate four values  pre_maxk, suf_maxk, pre_nmaxk, suf_nmaxk, which are 
pre_maxk  length of maximum prefix whose max element = k, similarly for suf_maxk, except we use suffix.
pre_nmaxk  length of maximum prefix whose max element < k, similarly for suf_nmaxk.
So while merging two slices of array we count the no of subarrays whose start index is in left slice and end index in right slice, we do it like this 
count += (left.suf_maxk) * (right.pre_maxk)  (left.suf_nmaxk) * (right.pre_nmaxk)
and the values of these four variables for the merged slice can also be calculated from the values of the left and right slices. So this dividing and combining part requires O(1) time, hence if divide left and right slices are of equal length then the complexity of this approach would be O(N).
answered
01 Feb, 18:38
2★hemanthvhr
1●1
accept rate:
100%