Prefix Scores :
Difficulty Level : Medium
Submissions : 222
Asked In :
Marks :15
: 5 | : 0
For an integer array $$$arr$$$ containing $$$k$$$ integers, we calculate the score as follows:
- For each $$$i$$$ from $$$1$$$ to $$$k$$$ in order, we add the current maximum element in the array to $$$arr[i]$$$
- The score of $$$arr$$$ is then defined as the sum of the elements of $$$arr$$$.
For example, if $$$arr = [2,1,3]$$$, we perform the following steps:
- Add the current maximum element, $$$3$$$ to $$$arr[1]$$$. Thus $$$arr=[5,1,3].$$$
- Add the current maximum element, $$$5$$$ to $$$arr[2]$$$. Thus $$$arr=[5,6,3].$$$
- Add the current maximum element, $$$6$$$ to $$$arr[3]$$$. Thus $$$arr=[5,6,9].$$$
You are given an integer array $$$A$$$ containing $$$n$$$ integers. Your task is to find the score of every prefix of the given array $$$A$$$.
The first line of input contains an integer $$$t \hspace{2pt} (1 \le t \le 10^4)$$$ — the number of testcases. The description of $$$t$$$ testcases follows.
The first line of each testcase contains an integer $$$n \hspace{2pt} (1 \le n \le 10^5)$$$ — the number of elements in the array $$$A$$$.
The second line of each testcase contains $$$n$$$ space separated integers $$$a_0, a_1, ... a_n$$$ $$$(0 \le a_i \le 10^9)$$$ — the elements of array $$$A$$$.
It is guaranteed that the sum of $$$n$$$ over all testcases does not exceed $$$10^5.$$$
For each testcase, print $$$n$$$ space separated integers — the $$$i^{th}$$$ integer should be the score of the prefix ending at index $$$i$$$. Since the scores can be rather large, print them modulo $$$10^9 + 7$$$.
231 2 331 2 1
2 8 19 2 8 14
In sample test case 1,
- The final value for the prefix $$$A[1..1]$$$ after applying the procedure = $$$[2]$$$. Hence the score is $$$2$$$.
- The final value for the prefix $$$A[1..2]$$$ after applying the procedure = $$$[3,5]$$$. Hence the score is $$$8$$$.
- The final value for the prefix $$$A[1..3]$$$ after applying the procedure = $$$[4,6,9]$$$. Hence the score is $$$19$$$.
