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

Auto comment: topic has been updated by Bhaskar13 (previous revision, new revision, compare).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

mistakes If arr is [-1, 5, 2, -8, 7, 101], then ans=18+606=624 instead of 43 + 101(5)=548