Maximize the sum of arr[i] times i

Problem Statement

Given an array of n positive integers, find the maximum value of Σ(arr[i] * i) where i is the index (0-indexed) after rearranging the array elements.

Constraints:

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

Example:

• Input: arr = [3, 5, 6, 1]
• Output: 31
• Explanation: Sorted order [1, 3, 5, 6] gives 1×0 + 3×1 + 5×2 + 6×3 = 0 + 3 + 10 + 18 = 31

Example 2:

• Input: arr = [2, 3, 1, 5, 4]
• Output: 40
• Explanation: Sorted [1, 2, 3, 4, 5] gives 0 + 2 + 6 + 12 + 20 = 40

Approach 1: Brute Force (Try All Permutations)

Intuition

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

Algorithm

1. Generate all permutations of the array
2. For each permutation, calculate Σ(arr[i] * i)
3. Return maximum sum

import java.util.*;

public class Solution {
    private long maxSum = Long.MIN_VALUE;
    
    private void permute(int[] arr, int start) {
        if (start == arr.length) {
            long sum = 0;
            for (int i = 0; i < arr.length; i++) {
                sum += (long) arr[i] * i;
            }
            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 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) to calculate sum for each
• Space Complexity: O(n) - For storing permutation

Approach 2: Greedy (Sort Ascending) - Optimal

Intuition

To maximize the weighted sum, larger elements should be placed at higher indices (to be multiplied by larger weights).

Key Insight: Sort the array in ascending order. This ensures:

• Smallest elements are at lowest indices (multiplied by small numbers)
• Largest elements are at highest indices (multiplied by large numbers)

Algorithm

1. Sort array in ascending order
2. Calculate sum = Σ(arr[i] * i)
3. Return sum

import java.util.*;

public class MaximizeSumOfArrI {
    
    public long maxSum(int[] arr) {
        int n = arr.length;
        
        // Sort in ascending order
        int[] sorted = arr.clone();
        Arrays.sort(sorted);
        
        long sum = 0;
        for (int i = 0; i < n; i++) {
            sum += (long) sorted[i] * i;
        }
        
        return sum;
    }
    
    public void explainSolution(int[] arr) {
        System.out.println("Original: " + Arrays.toString(arr));
        
        int[] sorted = arr.clone();
        Arrays.sort(sorted);
        System.out.println("Sorted: " + Arrays.toString(sorted));
        
        long sum = 0;
        System.out.print("Sum = ");
        for (int i = 0; i < sorted.length; i++) {
            long term = (long) sorted[i] * i;
            sum += term;
            if (i > 0) System.out.print(" + ");
            System.out.print(sorted[i] + "×" + i);
        }
        System.out.println(" = " + sum);
    }
    
    public static void main(String[] args) {
        MaximizeSumOfArrI ms = new MaximizeSumOfArrI();
        
        ms.explainSolution(new int[]{3, 5, 6, 1});
        System.out.println();
        ms.explainSolution(new int[]{2, 3, 1, 5, 4});
    }
}

Dry Run Example

Mathematical Proof

For any two elements a < b at positions i < j:

• Current contribution: a*i + b*j
• If swapped: b*i + a*j
• Difference: (a*i + b*j) - (b*i + a*j) = a*i - a*j + b*j - b*i = (b-a)*(j-i)

Since b > a and j > i, we have (b-a)*(j-i) > 0

This means: larger elements at higher indices is always better.

Complexity Analysis

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

Related: Minimize Sum

To minimize Σ(arr[i] * i), sort in descending order:

Key Takeaways

1. Greedy Sorting: Sort ascending to maximize weighted sum
2. Large × Large: Bigger elements should multiply with bigger indices
3. Simple Solution: Just sort and compute
4. Proof by Exchange: Swapping any two elements in sorted order reduces sum
5. Time Optimal: O(n log n) due to sorting
6. For Minimization: Sort in descending order instead
7. 0-indexed vs 1-indexed: Be careful with index starting point