I recently appeared for Google online assessment and received the following question. Could someone help me with the solution?
Question:
An water management system in made such that n tanks are connected linearly. The goodness of the i ^th tank is given by goodness[i]. The system goodness of a contiguous segment of tanks (i.e., a subsegment) is defined as the product of the number of tanks and the maximum goodness of the tanks in the segment.
Given the array goodness, find the sum of the system goodness of all the segments of the tanks. Since the answer can be large, report it modulo ( 10^9 + 7 ).
Example
Input:
n = 3
goodness = [3, 2, 3]Explanation:
| Subsegment | Number of Tanks | Maximum Goodness | System Goodness |
|---|---|---|---|
| [3] | 1 | 3 | 1 * 3 = 3 |
| [3, 2] | 2 | 3 | 2 * 3 = 6 |
| [3, 2, 3] | 3 | 3 | 3 * 3 = 9 |
| [2] | 1 | 2 | 1 * 2 = 2 |
| [2, 3] | 2 | 3 | 2 * 3 = 6 |
| [3] | 1 | 3 | 1 * 3 = 3 |
The sum of all system goodness is:
( 3 + 6 + 9 + 2 + 6 + 3 = 29 ).
Output:
29Function Description
Complete the function getSystemGoodnessSum in the editor below.
-
getSystemGoodnessSum takes the following arguments:
int goodness[n]: the goodness of the tanks
-
Returns:
int: the sum of system goodness over all the subsegments of tanks, modulo ( 10^9 + 7 ).
Constraints:
- ( 1 <= n <=10^5 )
- ( 1 <= goodness[i] <= 10^5 )