The problem:
Given an array $A$ of integers, $A[1], A[2], \dots, A[n]$, find a contiguous sub-array $A[i], \dots, A[j]$ such that $(j-i+1) \times \min\{A[i], \dots, A[j]\}$ is maximum.
Solution
This is a classic ACM programming contest problem.
A bunch of solutions can be found here: http://www.informatik.uni-ulm.de/acm/Locals/2003/html/judge.html
Look at Problem H.
But, the reason for this blog post was to present a different solution to this, using Cartesian Trees.
A cartesian tree for an array $A$, is a binary tree such that it is a heap formed from the elements of $A$, and the in-order traversal of the tree gives back the array in order: $A[1], A[2], \dots, A[n]$. See the diagram below (swiped from the wiki page).
These trees can be constructed in $O(n)$ time (see the wiki page for more details).
To solve the problem, we use divide and conquer.
First we construct a cartesian tree which gives a min-heap.
Now notice that, if $A[m]$ is the minimum element of $A$, then the optimum solution is either $n \times A[m]$, or the optimum solutions from $A[1], \dots A[m-1]$ and $A[m+1], \dots, A[n]$.
The cartesian tree of $A$ gives us $m$, and the cartesian trees for $A[1], \dots, A[m-1]$ (the left subtree) and $A[m+1], \dots, A[n]$ (the right sub-tree)!
Thus if we annotate each node $N$ of the cartesian tree with the number of nodes in that sub-tree $N_c$, we just need to compute max of $N.values \times N_c$ over all the nodes! $N.value$ is the element value from $A$.
This is an $O(n)$ time solution.
For another application of Cartesian trees, try solving this puzzle on this blog: Construct BST.
Given an array $A$ of integers, $A[1], A[2], \dots, A[n]$, find a contiguous sub-array $A[i], \dots, A[j]$ such that $(j-i+1) \times \min\{A[i], \dots, A[j]\}$ is maximum.
Solution
This is a classic ACM programming contest problem.
A bunch of solutions can be found here: http://www.informatik.uni-ulm.de/acm/Locals/2003/html/judge.html
Look at Problem H.
But, the reason for this blog post was to present a different solution to this, using Cartesian Trees.
A cartesian tree for an array $A$, is a binary tree such that it is a heap formed from the elements of $A$, and the in-order traversal of the tree gives back the array in order: $A[1], A[2], \dots, A[n]$. See the diagram below (swiped from the wiki page).
These trees can be constructed in $O(n)$ time (see the wiki page for more details).
To solve the problem, we use divide and conquer.
First we construct a cartesian tree which gives a min-heap.
Now notice that, if $A[m]$ is the minimum element of $A$, then the optimum solution is either $n \times A[m]$, or the optimum solutions from $A[1], \dots A[m-1]$ and $A[m+1], \dots, A[n]$.
The cartesian tree of $A$ gives us $m$, and the cartesian trees for $A[1], \dots, A[m-1]$ (the left subtree) and $A[m+1], \dots, A[n]$ (the right sub-tree)!
Thus if we annotate each node $N$ of the cartesian tree with the number of nodes in that sub-tree $N_c$, we just need to compute max of $N.values \times N_c$ over all the nodes! $N.value$ is the element value from $A$.
This is an $O(n)$ time solution.
For another application of Cartesian trees, try solving this puzzle on this blog: Construct BST.
No comments:
Post a Comment