Maximize array sum after K negations 🔥 🔥 | Love Babbar DSA Sheet | Greedy

Please like, share and subscribe if you found the video useful. Feel free to ask in comments section if you have any doubts. :)

#Greedy

[Saurabh-febg]

This question is really amazing and explanation is on point., Appreciated!!

[Raj]

at 15:11 we will simply break out first but then check if k is odd then we have to subtract the first value from the sum otherwise simply ans the sum

[Saurabh-febg]

Hi ayushi... I am following u and also trying to put in some 40-50 minutes on the question before seeing for the solution. Hopefully I am able to solve a lot of questions by myself. But the only problem I am facing is less nom of test cases.

Here, you took the very great test case to come up with the approach in the first go itself.

So, In case I am not coming with the right approach should I ask the interviewer to give more nom of test case or think by myself??

[Raj]

Bhot hi acha question the bhut sare cases sochne pade maza ayaa :-
my code submitted in gfg
long long int maximizeSum(long long int arr[], int n, int k)
{

sort(arr, arr+n);

int i;
for( i = 0 ; i < n ; i++)
{

if(arr[i] > 0 || k == 0 || arr[i] == 0) break;

if(arr[i]<0)
{
arr[i] = arr[i]*-1;
k--;

}


}

long long int sum = 0;
for(int i = 0 ; i < n ; i++)
{
sum = sum + arr[i];
}


if(i== 1 && k==0) return sum; // fisrt pe hi aakke k ktam ho gya

if(i == 0 && k%2==0) //all positive with k is even
return sum;
else if ( i==0 && k%2!=0 )
{
return (sum - 2*arr[0]); //when k is odd
}


if(arr[i]==0) //agar kahi 0 mil gya to bas sra k wahi kha jyega agar ku6 bacha hoga to
return sum;

if( k%2==0) return sum; //agar k even hua ya 0 hua koi v case return sum seedha

int mini = min(arr[i], arr[i-1]); // jab k odd hoga tab mini ko gtana hoga

return sum-(2*mini);


}