A span of an integer array is the difference of the maximum and the minimum elements.
For example, span of $[3,4,8,1,-1]$ is $8 - (-1) = 9$. The span of a single element array is $0$.
Given an array $A$ of $n$ integers, can you find the sum of spans of all the subarrays of $A$? (subarray is a contiguous subset). For example $[4,8,1]$ is a sub-array of $[3,4,8,1,-1]$ and $[4,8,1, 5]$ etc.
Try for an algorithm which runs in $O(n)$ time.
[Solution]
For example, span of $[3,4,8,1,-1]$ is $8 - (-1) = 9$. The span of a single element array is $0$.
Given an array $A$ of $n$ integers, can you find the sum of spans of all the subarrays of $A$? (subarray is a contiguous subset). For example $[4,8,1]$ is a sub-array of $[3,4,8,1,-1]$ and $[4,8,1, 5]$ etc.
Try for an algorithm which runs in $O(n)$ time.
[Solution]
No comments:
Post a Comment