Only removal of elements is allowed(no reordering/sorting)
e.g:
Let the array be [-1, 5, 2, -8, 7]
then using all elements sum = -1*1 + 5*2 + 2*3 + -8*4 + 7*5 = 18
removing -1, -8 sum = 5*1+2*2+7*3 = 30
removing only -8 sum =-1*1 + 5*2 + 2*3 + 7*4 = 43(ans)
If arr is [-1, 5, 2, -8, 7, 101], then ans =30 + 606 = 636 instead of 43 + 101(5)=548
I thought of this below strategy
going from last ele to first in array, If that ele >=0 or remSum + (i+1)*a[i] >=0,
I will add the ele to a list at 0 index
where remSum =0 initially or sum of elements already to list
using this, I will add 5 to list first;for ele = -8, 4(-8) + 7 >= 0 false, I willnot add it to list.Later I will add 2, 5, then list will be [2,3,5]. For -1, -1*1+(2+3+5)>=0 true, so I will add to list, [-1,5,2,7] 43 ans
for second arr, 101+7+4(-8)>=0, so I will add to list
I was assuming intial elements are present, that's why i am multiplying a[i] with (i+1) instead of number of elements present(which I didn't find)
My friend was asked this in a test. If someone can discuss correct strategy or point me to already existing editorial/problem in codeforces or any other CP site, it would be great
We can have a 2-d DP where dp[i][j] denotes the maximum sum from 1 to i (1-based indexing) such that we have deleted exactly j elements from 1 to i. The recurrence relation is therefore DP[i][j] = MAX(dp[i-1][j]+val, dp[i-1][j-1]) where val is (i-j)*arr[j] and the final ans is MAX{dp[N]}
EDIT: This approach is wrong
Notice that taking an element increase the sum of the array by sum of all the elements in suffix(don't count the elements which we have already decided to not keep in the array) starting from that element (i+1 increases by 1 for all the elements ahead and the current element is added). So if this is positive use that element, otherwise don't.
In the 1st array
sum from 7 = 7 (>0), use it
sum from 8 = -1 (<0), don't use it
sum from 2 = 2+7 = 9 (>0), use it
sum from 5 = 2+7+5 (>0), use it
sum from -1 = -1+2+7+5 (>0), use it
when I solved this way for
{ -1, 5, 2, -4, 7 }, it gave 34
but
{ -1, 5, 2, 7 } clearly gives 43
My bad, that was a really stupid mistake.
How about this. We maintain 2 variables, totalSum and sum. totalSum is sum including the weights (multiplied with i+1) and sum is just their sum. So now iterate from last to first again and if(totalSum+sum+currentElement>totalSum) use the current element and make totalSum = totalSum + sum + current element and make sum = sum + currentElement.
Finally totalSum should give you correct answer.
totalSum+sum+currentElement>totalSum
IS this intentional
sum+currentElement>0
This is not diffrent from your 1st comment
K
I am a retard. ig O(n^2) dp is the answer then
That's CF573E