Array-value greedy tricks — k negations, arr[i]*i, abs-diff sum, three-stack equal sum

Medium

Problem

Four short greedy problems:

Maximise the array sum after exactly k negations (you may negate the same element more than once). Maximise Σ arr[i]·i by rearranging the array. Arrange the array to maximise the sum of absolute differences between neighbours, treated as a circle. Remove top elements from three stacks until their sums are equal and as large as possible.

Example 1

Input:  k negations: [-2, 0, 5, -1, 2], k = 4
Output: 10

Example 2

Input:  arr[i]*i: [3, 5, 6, 1]
Output: 31

Sorted [1, 3, 5, 6]: 0 + 3 + 10 + 18.

Also asked as: Maximize array sum after K negations · Maximize the sum of arr[i]*i · Maximum sum of absolute difference of an array · Maximize sum of consecutive differences in a circular array · Find maximum sum possible equal sum of three stacks · Maximum product subset of an array

Test cases

Case 1

Input:    [-2,0,5,-1,2], 4
Expected: 10

Case 2

Input:    [-1,-2], 2
Expected: 3

Case 3

Input:    [1,2,3], 1
Expected: 4

Case 4

Input:    [5], 2
Expected: 5

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
View solutionHide solution2 approaches

1. K negations — flip the most negative each time

Time O(n log n)Space O(1)

Sort ascending; flip negatives left to right while k remains. If k is still odd afterwards, flip the current smallest absolute value once.

function maxSumAfterKNegations(a, k) {
a.sort((x, y) => x - y);
for (let i = 0; i < a.length && k > 0 && a[i] < 0; i++) { a[i] = -a[i]; k--; }
if (k % 2 === 1) { const m = Math.min(...a); const idx = a.indexOf(m); a[idx] = -a[idx]; }
return a.reduce((s, v) => s + v, 0);
}

2. Maximise Σ arr[i]·i — sort ascending

Time O(n log n)Space O(1)

Larger values deserve larger indices, so sorting ascending maximises the weighted sum (rearrangement inequality).

function maxSumIndexProduct(a) {
a.sort((x, y) => x - y);
return a.reduce((s, v, i) => s + v * i, 0);
}

Max sum of |arr[i]−arr[i+1]| over an arrangement: sort, then interleave the small and large halves (zig-zag). Three stacks equal sum: prefix-sum each stack from the top, pop the largest total until all three match. Max product subset: multiply all non-zero elements; if the count of negatives is odd, divide out the largest (least-magnitude) negative.