Maximize the sum of arr[i] times i

The problem, simply

You get a row of numbers. You may put them in any order. Then each number is multiplied by its position, counting from 0: the first number by 0, the second by 1, and so on. Add up all the products.

Give back the biggest total you can make. In code it is the biggest value of arr[0] * 0 + arr[1] * 1 + ... + arr[n - 1] * (n - 1).

A story to remember it

Picture it

Examples

Way 1: the simple way

Try every order of the cards, work out the total for each, and keep the best.

1. Build every order with swaps, one position at a time.
2. For a full order, add a[i] * i for every i.
3. Keep the biggest total.

class Solution {
    private long best;

    public long maxIndexSum(int[] a) {
        best = Long.MIN_VALUE;
        tryOrders(a, 0);
        return best;
    }

    private void tryOrders(int[] a, int start) {
        if (start == a.length) {
            long total = 0;
            for (int i = 0; i < a.length; i++) total += (long) a[i] * i;
            best = Math.max(best, total);
            return;
        }
        for (int i = start; i < a.length; i++) {
            swap(a, start, i);
            tryOrders(a, start + 1);
            swap(a, start, i);
        }
    }

    private void swap(int[] a, int i, int j) { int t = a[i]; a[i] = a[j]; a[j] = t; }
}

How long it takes: n! orders, each added up in n steps, so O(n! * n). Extra room: the recursion is n deep, O(n).

Way 2: the clever way

Think about two cards, a small one s and a big one b, in two boxes i < j. If the big card is in the big box, they give s * i + b * j. If you swap them, they give b * i + s * j. The difference is (b - s) * (j - i), which is never negative. So a big card in a small box is always a mistake you can fix by swapping. Keep fixing and you end with the cards sorted.

1. Sort the cards from small to big.
2. Add a[i] * i for every box i.

import java.util.Arrays;

class Solution {
    public long maxIndexSum(int[] a) {
        Arrays.sort(a);                       // small cards in small boxes
        long total = 0;
        for (int i = 0; i < a.length; i++) {
            total += (long) a[i] * i;         // card times box number
        }
        return total;
    }
}

How long it takes: the sort is O(n log n) and the adding is O(n). Extra room: O(1) beyond the sort.

Watch out for

• Boxes start at 0, not 1. If the problem counts from 1, the order is the same but the total is bigger by the sum of all cards.
• Negative cards need no special care. Sorting puts the most negative one in box 0, where it costs nothing.
• Do not sort from big to small. That gives the smallest total, not the biggest.

What interviewers ask next

• Minimise the total instead? Sort from big to small, so the biggest card sits in box 0.
• You may only rotate the row, not reorder it. Find the best rotation in O(n): each rotation by one place changes the total by sum - n * x, where x is the card that moves from the last box to box 0.
• Pair two rows to make the biggest sum of products. Sort both the same way. This is the rearrangement inequality, the same exchange idea.
• Why is the swap argument enough? Any order that is not sorted has a neighbouring pair in the wrong order, and swapping it never lowers the total, so you can walk to the sorted order without ever losing.

Remember this

Grown-up words: the boxes are array indices, the steps game is a weighted sum, the swap trick is an exchange argument, and sorting both rows the same way is the rearrangement inequality.