How to find subset of array such that Σ(i+1)*a[i] is maximum(Only removal of elements is allowed)

Revision en3, by Bhaskar13, 2020-06-03 00:30:55

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

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en4 English Bhaskar13 2020-06-03 00:32:11 1 Tiny change: 'that ele >0 or remSu' -> 'that ele >=0 or remSu'
en3 English Bhaskar13 2020-06-03 00:30:55 97
en2 English Bhaskar13 2020-06-03 00:29:15 5 Tiny change: 'g/sorting)\ne.g:\nLe' -> 'g/sorting) <br>\ne.g:\nLe'
en1 English Bhaskar13 2020-06-03 00:28:03 1291 Initial revision (published)