Maximum sum of absolute difference of an array

Problem Statement

Given an array of n distinct integers, find the maximum sum of absolute differences between consecutive elements after rearranging the array.

Formula: Maximize Σ|arr[i] - arr[i+1]| for i from 0 to n-2, plus |arr[n-1] - arr[0]| (circular).

Or equivalently: Maximize |a0-a1| + |a1-a2| + ... + |a(n-2)-a(n-1)| + |a(n-1)-a0|

Constraints:

• 1 ≤ n ≤ 10^5
• 1 ≤ arr[i] ≤ 10^9

Example:

• Input: arr = [1, 2, 4, 8]
• Output: 18
• Explanation: Arrange as [1, 8, 2, 4] → |1-8| + |8-2| + |2-4| + |4-1| = 7 + 6 + 2 + 3 = 18

Example 2:

• Input: arr = [1, 2, 3, 4]
• Output: 8
• Explanation: [1, 3, 2, 4] or [2, 4, 1, 3] → |1-3| + |3-2| + |2-4| + |4-1| = 2 + 1 + 2 + 3 = 8

Approach 1: Brute Force (Try All Permutations)

Intuition

Try all possible arrangements of the array and calculate the sum of absolute differences for each. Track the maximum sum.

Algorithm

1. Generate all permutations of the array
2. For each permutation, calculate circular sum of absolute differences
3. Return maximum sum

import java.util.*;

public class Solution {
    private long maxSum = Long.MIN_VALUE;
    
    private long calculateSum(int[] arr) {
        int n = arr.length;
        long sum = 0;
        for (int i = 0; i < n; i++) {
            sum += Math.abs(arr[i] - arr[(i + 1) % n]);
        }
        return sum;
    }
    
    private void permute(int[] arr, int start) {
        if (start == arr.length) {
            maxSum = Math.max(maxSum, calculateSum(arr));
            return;
        }
        
        for (int i = start; i < arr.length; i++) {
            swap(arr, start, i);
            permute(arr, start + 1);
            swap(arr, start, i);
        }
    }
    
    private void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
    
    public long maxSumBrute(int[] arr) {
        maxSum = Long.MIN_VALUE;
        permute(arr.clone(), 0);
        return maxSum;
    }
}

Complexity Analysis

• Time Complexity: O(n! * n) - n! permutations, O(n) calculation each
• Space Complexity: O(n) - For permutation storage

Approach 2: Greedy (Zigzag Arrangement) - Optimal

Intuition

To maximize absolute differences, arrange elements in a zigzag pattern: alternate between smallest and largest elements.

Pattern: small, large, small, large, ... Or: large, small, large, small, ...

Key Insight: In the optimal arrangement:

• Each element appears in exactly 2 differences (one with left neighbor, one with right)
• To maximize, pair small elements with large elements
• The result is: 2 * (sum of larger half - sum of smaller half)

Algorithm

1. Sort the array
2. Divide into two halves: smaller and larger
3. Result = 2 * (sum of larger half - sum of smaller half)

import java.util.*;

public class MaxAbsoluteDifferenceSum {
    
    public long maxSum(int[] arr) {
        int n = arr.length;
        
        // Sort the array
        int[] sorted = arr.clone();
        Arrays.sort(sorted);
        
        // Sum of larger half minus sum of smaller half, times 2
        long smallSum = 0, largeSum = 0;
        
        for (int i = 0; i < n / 2; i++) {
            smallSum += sorted[i];
        }
        
        for (int i = n / 2; i < n; i++) {
            largeSum += sorted[i];
        }
        
        return 2 * (largeSum - smallSum);
    }
    
    public int[] getOptimalArrangement(int[] arr) {
        int n = arr.length;
        int[] sorted = arr.clone();
        Arrays.sort(sorted);
        
        // Build zigzag arrangement
        int[] result = new int[n];
        int left = 0, right = n - 1;
        int idx = 0;
        
        while (left <= right) {
            if (idx < n) result[idx++] = sorted[left++];
            if (idx < n) result[idx++] = sorted[right--];
        }
        
        return result;
    }
    
    public static void main(String[] args) {
        MaxAbsoluteDifferenceSum mads = new MaxAbsoluteDifferenceSum();
        
        System.out.println(mads.maxSum(new int[]{1, 2, 4, 8}));  // 18
        System.out.println(mads.maxSum(new int[]{1, 2, 3, 4}));  // 8
        
        System.out.println("Optimal arrangement: " + 
            Arrays.toString(mads.getOptimalArrangement(new int[]{1, 2, 4, 8})));
    }
}

Dry Run Example

Why Formula Works

In the optimal zigzag arrangement:

• Each element from the smaller half is adjacent to elements from the larger half
• Each element contributes to exactly 2 differences
• The sum becomes: 2 × (each large element) - 2 × (each small element)
• Which equals: 2 × (sum of large half - sum of small half)

Complexity Analysis

• Time Complexity: O(n log n) - Dominated by sorting
• Space Complexity: O(n) for sorted array (or O(1) if sorting in place)

Edge Cases

| Case | Array | Result | |------|-------|--------| | Two elements | [1, 5] | 2 × (5-1) = 8 | | Three elements | [1, 2, 3] | 2 × (3 - 1) = 4 | | All same | [5, 5, 5] | 0 |

Key Takeaways

1. Zigzag Pattern: Alternate between small and large elements
2. Formula: 2 × (sum of larger half - sum of smaller half)
3. Circular Sum: Don't forget the wrap-around difference
4. Each Element Twice: Every element appears in exactly 2 differences
5. Sort First: Sorting divides elements into smaller and larger halves
6. O(n log n): Optimal complexity due to sorting
7. Greedy Proof: Pairing small with large maximizes each difference