Please, try EDU on Codeforces! New educational section with videos, subtitles, texts, and problems. ×

By Bhaskar13, history, 5 weeks ago, ,

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

• +2

 » 5 weeks ago, # |   0 Auto comment: topic has been updated by Bhaskar13 (previous revision, new revision, compare).
 » 5 weeks ago, # |   0 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]}
 » 5 weeks ago, # | ← Rev. 4 →   +5 EDIT: This approach is wrongNotice 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 arraysum from 7 = 7 (>0), use itsum from 8 = -1 (<0), don't use itsum from 2 = 2+7 = 9 (>0), use itsum from 5 = 2+7+5 (>0), use itsum from -1 = -1+2+7+5 (>0), use it
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   0 when I solved this way for { -1, 5, 2, -4, 7 }, it gave 34 but { -1, 5, 2, 7 } clearly gives 43
•  » » » 4 weeks ago, # ^ |   0 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.
•  » » » » 4 weeks ago, # ^ |   0 totalSum+sum+currentElement>totalSum IS this intentional sum+currentElement>0 This is not diffrent from your 1st comment
•  » » » » » 4 weeks ago, # ^ |   0 KI am a retard. ig O(n^2) dp is the answer then
 » 4 weeks ago, # |   +3 That's CF573E
 » 4 weeks ago, # |   0 mistakes If arr is [-1, 5, 2, -8, 7, 101], then ans=18+606=624 instead of 43 + 101(5)=548
 » 4 weeks ago, # | ← Rev. 3 →   0 public static int myStrategy(int[] arr) { int n = arr.length; int remSum=0; List list =new ArrayList<>(); for(int i=n-1;i>=0;i--) { if((i+1)*arr[i]+remSum>=0) { list.add(0,arr[i]); remSum +=arr[i]; } } int ans=0; for(int i=0;i