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