Maximum Subsequence Sum
All submissions for this problem are available.### Read problems statements in [Hindi](http://www.codechef.com/download/translated/COOK115/hindi/CYCLCSUM.pdf), [Mandarin Chinese](http://www.codechef.com/download/translated/COOK115/mandarin/CYCLCSUM.pdf), [Russian](http://www.codechef.com/download/translated/COOK115/russian/CYCLCSUM.pdf), [Vietnamese](http://www.codechef.com/download/translated/COOK115/vietnamese/CYCLCSUM.pdf), and [Bengali](http://www.codechef.com/download/translated/COOK115/bengali/CYCLCSUM.pdf) as well. Chef has a machine which he uses to rotate sequences. If he puts a sequence $S_1, S_2, \ldots, S_N$ into the machine, it produces the sequence $S_2, S_3, \ldots, S_N, S_1$, i.e. the first element of the sequence is moved to the end. Chef is definitely not a newbie ― he knows about trivial things like finding the maximum sum of a contiguous subsequence. Therefore, he now made a difficult problem to challenge himself: You are given a sequence $A_1, A_2, \ldots, A_N$. For each $k$ ($0 \le k \le N-1$), consider the sequence produced by inserting it into the machine repeatedly $k$ times (i.e. inserting $A$ into the machine and replacing $A$ by the sequence it produces, $k$ times); find the maximum sum of a non empty contiguous subsequence of this sequence. However, to solve this problem, Chef needs the help of a pro. Solve it for him. ### Input - The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows. - The first line of each test case contains a single integer $N$. - The second line contains $N$ space-separated integers $A_1, A_2, \ldots, A_N$. ### Output For each test case, print a single line containing $N$ space-separated integers. For each valid $i$, the $i$-th of these integers should denote the largest sum of a non empty contiguous subsequence of the sequence produced by the machine after $i-1$ repeated insertions. ### Constraints - $1 \le T \le 100$ - $1 \le N \le 5 \cdot 10^5$ - $|A_i| \le 10^9$ for each valid $i$ - the sum of $N$ over all test cases does not exceed $5 \cdot 10^5$ ### Example Input ``` 1 4 -5 4 1 2 ``` ### Example Output ``` 7 7 4 5 ``` ### Explanation **Example case 1:** - After zero insertions, $A = [-5, 4, 1, 2]$. The contiguous subsequence with the maximum sum is $A = [4, 1, 2]$. - After one insertion, $A = [4, 1, 2, -5]$. The contiguous subsequence with the maximum sum is $A = [4, 1, 2]$. - After two insertions, $A = [1, 2, -5, 4]$. The contiguous subsequence with the maximum sum is $A = $. - After three insertions, $A = [2, -5, 4, 1]$. The contiguous subsequence with the maximum sum is $A = [4, 1]$.
|Tags||akashbhalotia, cook115, easy-medium, max-sub-arrays, prefix, reviveddevil, suffix|
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, SQL, kotlin, PERL6, TEXT, CPP17, SCM chicken, PYP3, CLOJ, R, COB, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.