The problem was here.
In short, compute the total of the spans for each sub-array of a given array, the span of an array being the difference between the maximum and minimum element of the array.
Solution
Note that it is enough to figure out the sum the maximum elements of each array [and minimum, and then take the difference].
Suppose we want to find the max sum of sub-arrays of an array $A[1,\dots,n]$, and the maximum element of $A$ appears at $A[M]$. Assume the elements are distinct for now, but does not really matter.
Now $A[M]$ is the maximum of any subarray $A[i,\dots,j]$ where $i \le M \le j$ and thus contributes $A[M]\times M \times (n-M+1)$ to the total we seek.
Now we recursively compute the totals for $A[1,\dots,M-1]$ and $A[M+1,\dots,n]$ and add all those up.
This can be done in $O(n)$ time, if we compute the cartesian tree corresponding to the array (which can be done in $O(n)$ time).
The cartesian tree is basically a max-heap whose inorder traversal gives back the array in the order $A[1], A[2], \dots$. The whole tree corresponds to $A[1, \dots, n]$, while the left subtree of the root corresponds to $A[1, \dots, M-1]$ and the right sub-tree corresponds to $A[M+1, \dots, n]$.
In order to get past the distinctness assumption, we can work with $B[i] = (A[i], i)$ instead.
[See: http://ruffnsluff.blogspot.com/2015/05/max-area-in-histogram-solution.html for an explanation of Cartesian trees. There is a diagram too!]
In short, compute the total of the spans for each sub-array of a given array, the span of an array being the difference between the maximum and minimum element of the array.
Solution
Note that it is enough to figure out the sum the maximum elements of each array [and minimum, and then take the difference].
Suppose we want to find the max sum of sub-arrays of an array $A[1,\dots,n]$, and the maximum element of $A$ appears at $A[M]$. Assume the elements are distinct for now, but does not really matter.
Now $A[M]$ is the maximum of any subarray $A[i,\dots,j]$ where $i \le M \le j$ and thus contributes $A[M]\times M \times (n-M+1)$ to the total we seek.
Now we recursively compute the totals for $A[1,\dots,M-1]$ and $A[M+1,\dots,n]$ and add all those up.
This can be done in $O(n)$ time, if we compute the cartesian tree corresponding to the array (which can be done in $O(n)$ time).
The cartesian tree is basically a max-heap whose inorder traversal gives back the array in the order $A[1], A[2], \dots$. The whole tree corresponds to $A[1, \dots, n]$, while the left subtree of the root corresponds to $A[1, \dots, M-1]$ and the right sub-tree corresponds to $A[M+1, \dots, n]$.
In order to get past the distinctness assumption, we can work with $B[i] = (A[i], i)$ instead.
[See: http://ruffnsluff.blogspot.com/2015/05/max-area-in-histogram-solution.html for an explanation of Cartesian trees. There is a diagram too!]
No comments:
Post a Comment