Swap and Maximize

JavaView on GFG

Intuition

Maximize sum of arr[i]*arr[i+1] for adjacent pairs by rearranging array.

Algorithm

1Sort array. Place in alternating pattern: large values at even positions, small at odd (or similar interleaving).

Common Pitfalls

•Sort and place: to maximize sum of adjacent products, interleave largest and second-largest alternately.

Swap and Maximize.java

Java

// Approach: Sort array. Pair largest with smallest alternately to maximize the swapped sum.
// Time: O(n log n) Space: O(1)
class Solution {
    public long maxSum(Long[] arr) {
        Arrays.sort(arr);
        int n = arr.length;
        long sum = 0;
        for (int i = 0, j = n - 1; i < n && j >= 0; i++, j--)
            sum += Math.abs(arr[i] - arr[j]);

        return sum;
    }
}

Was this solution helpful?