## Friday, October 21, 2016

### Maximize array sum after K negations - GeeksforGeeks

Maximize array sum after K negations - GeeksforGeeks
Given an array of size n and a number k. We must modify array K number of times. Here modify array means in each operation we can replace any array element arr[i] by -arr[i]. We need to perform this operation in such a way that after K operations, sum of array must be maximum?

Use PriorityQueue
we just have to replace the minimum element arr[i] in array by -arr[i] for current operation. In this way we can make sum of array maximum after K operations. Once interesting case is, once minimum element becomes 0, we don’t need to make any more changes.
`// This function does k operations on array`
`// in a way that maximize the array sum.`
`// index --> stores the index of current minimum`
`//           element for j'th operation`
`int` `maximumSum(``int` `arr[], ``int` `n, ``int` `k)`
`{`
`    ``// Modify array K number of times`
`    ``for` `(``int` `i=1; i<=k; i++)`
`    ``{`
`        ``int` `min = INT_MAX;`
`        ``int` `index = -1;`

`        ``// Find minimum element in array for`
`        ``// current operation and modify it`
`        ``// i.e; arr[j] --> -arr[j]`
`        ``for` `(``int` `j=0; j<n; j++)`
`        ``{`
`            ``if` `(arr[j] < min)`
`            ``{`
`                ``min = arr[j];`
`                ``index = j;`
`            ``}`
`        ``}`

`        ``// this the condition if we find 0 as`
`        ``// minimum element, so it will useless to`
`        ``// replace 0 by -(0) for remaining operations`
`        ``if` `(min == 0)`
`            ``break``;`

`        ``// Modify element of array`
`        ``arr[index] = -arr[index];`
`    ``}`

`    ``// Calculate sum of array`
`    ``int` `sum = 0;`
`    ``for` `(``int` `i=0; i<n; i++)`
`        ``sum += arr[i];`
`    ``return` `sum;`
`}`