Maximize Array Value After Rearrangement

JavaView on GFG

Intuition

Rearrange array to maximize sum of |arr[i]-arr[i-1]|. Sort and interleave min/max pattern.

Algorithm

1Sort. Place first half in even positions, second half in odd positions (or interleave min/max alternately).

Common Pitfalls

•Maximum sum of absolute differences: sort then rearrange in valley-peak pattern. Final sum = 2*(max_half - min_half).

Maximize Array Value After Rearrangement.java

Java

// Approach: Sort array and positions, then greedily assign largest values to positions with highest multipliers.
// Time: O(n log n) Space: O(1)
import java.util.*;

class Solution {

    int Maximize(int arr[]) {
        Arrays.sort(arr);
        
        long sum = 0; 
        int mod = (int)1e9 + 7;
        
        for(int i = 0; i < arr.length; i++)
            sum = (sum + (long)arr[i] * i) % mod;
        
        return (int)sum;
    }
}

Was this solution helpful?