WEIGHT - Weighted Sum
You are given N integers, A to A[N]. You have to assign weights to these integers such that their weighted sum is maximized. The weights should satisfy the following conditions :
- Each weight should be an positive integer.
- W = 1
- W[i] should be in the range [2, W[i-1] + 1] for i > 1
Weighted sum is defined as S = A * W + A * W + ... + A[N] * W[N]
There are multiple test cases.
First line contains the number of test cases
Each test case consists of a single line containing N.
This is followed by N lines, each containing A[i]
For each test case, output one line - the maximum weighted sum.
The weights are 1,2,3,2
N <= 10^6
| A[i] | <= 10^6
Total number of test cases is around 10.
The solution is more clear reversing the array
@Shahbaz Khan Thanks, your commment helped.I almost gave up on finding a bug in my solution.
please explain o(n) approach a bit
think of kadane
Can someone tell me how to solve it in O(n), please?
working for all the test cases specified in the comment and the forum still wa plz help
awesome problem.No need for DP.
Even with o(n)..got TLE..any suggestions??
I got an O(n) solution, seems to be valid on all given and commented test cases. But still WA? And it does not need Fast IO. Am I doing it wrong?