Only removal of elements is allowed(no reordering/sorting) <br>↵
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↵
↵
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↵
↵
