Array-value greedy tricks — k negations, arr[i]*i, abs-diff sum, three-stack equal sum
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
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.