Maximize sum of consecutive differences in a circular array

Problem Statement

Given an array of n elements, arrange the elements in a circular array such that the sum of absolute differences of consecutive elements is maximized.

In a circular array, the first element is also adjacent to the last element.

Constraints:

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

Example:

• Input: arr = [4, 2, 1, 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: Arrange as [1, 3, 2, 4]: |1-3| + |3-2| + |2-4| + |4-1| = 2 + 1 + 2 + 3 = 8. Or [2, 4, 1, 3]: |2-4| + |4-1| + |1-3| + |3-2| = 2 + 3 + 2 + 1 = 8

Approach 1: Brute Force (All Permutations)

Intuition

Generate all possible permutations of the array and calculate the sum of absolute differences for each circular arrangement. Return the maximum sum.

Algorithm

1. Generate all permutations of the array
2. For each permutation, calculate sum of |arr[i] - arr[i+1]| for all i
3. Don't forget to add |arr[n-1] - arr[0]| for circular property
4. Track and return maximum sum

import java.util.*;

public class Solution {
    private int maxSum = 0;
    
    private void permute(int[] arr, int start) {
        if (start == arr.length) {
            int sum = 0;
            int n = arr.length;
            for (int i = 0; i < n; i++) {
                sum += Math.abs(arr[i] - arr[(i + 1) % n]);
            }
            maxSum = Math.max(maxSum, sum);
            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 int maxCircularSum(int[] arr) {
        maxSum = 0;
        permute(arr, 0);
        return maxSum;
    }
}

Complexity Analysis

• Time Complexity: O(n!) - Generating all permutations
• Space Complexity: O(n) - Recursion stack depth

Approach 2: Greedy with Sorting (Optimal)

Intuition

To maximize the sum of absolute differences, we want to place elements such that each element is adjacent to elements far from it in value. The optimal strategy is:

1. Sort the array
2. Place smaller half elements at even positions and larger half at odd positions (or vice versa)
3. This ensures each element is adjacent to elements from the opposite half

Key Insight: After sorting, if we arrange elements as: smallest, largest, 2nd smallest, 2nd largest, ... each element contributes to two differences. The optimal arrangement makes each element appear twice - once as a "small" and once as a "large" neighbor.

The sum equals 2 * (sum of larger half - sum of smaller half).

Algorithm

1. Sort the array
2. Calculate sum of first half (smaller elements)
3. Calculate sum of second half (larger elements)
4. Return 2 * (larger_sum - smaller_sum)

import java.util.*;

public class Solution {
    public long maxCircularSum(int[] arr) {
        int n = arr.length;
        if (n <= 1) return 0;
        
        Arrays.sort(arr);
        
        long smallSum = 0, largeSum = 0;
        
        for (int i = 0; i < n / 2; i++) {
            smallSum += arr[i];
        }
        
        for (int i = n / 2; i < n; i++) {
            largeSum += arr[i];
        }
        
        return 2 * (largeSum - smallSum);
    }
    
    public static void main(String[] args) {
        Solution sol = new Solution();
        int[] arr = {4, 2, 1, 8};
        System.out.println(sol.maxCircularSum(arr));  // Output: 18
    }
}

Dry Run Example

Complexity Analysis

• Time Complexity: O(n log n) - Dominated by sorting
• Space Complexity: O(1) - Only using constant extra space (or O(n) depending on sort implementation)

Key Takeaways

1. Greedy Insight: To maximize differences, pair small elements with large elements
2. Mathematical Property: Each element contributes to exactly 2 differences in a circular array
3. Sorting Strategy: Sort and divide into halves - smaller half subtracts, larger half adds
4. Formula: Result = 2 * (sum of larger half - sum of smaller half)
5. Edge Cases: Arrays with 0 or 1 element return 0
6. Pattern: This is a classic "maximize difference" greedy problem where sorting reveals the optimal structure