Max sum in the configuration

JavaView on GFG

Time: O(n)

Space: O(1)

Intuition

Maximize sum of i*arr[i] over all rotations. Derive from initial sum using formula.

Algorithm

1Compute initial sum S0. For rotation r+1: Sr+1 = Sr + totalSum - n*arr[n-1-r].
2Track maximum over all rotations.

Common Pitfalls

•O(n) by deriving each rotation sum from previous. Initial O(n) setup then O(n) iterations.

Max sum in the configuration.java

Java

// Approach: For rotation by k: sum(k) = sum(k-1) + totalSum - n*arr[n-k]. Use prefix sum to compute efficiently.
// Time: O(n) Space: O(1)
class Solution {
    int maxSum(int[] arr) {
        int sum = 0;
        for (int i = 0; i < arr.length; i++)
            sum += (arr[i] * i);

        for (int i = 1; i < arr.length; i++)
            sum = Math.max(sum, rot(arr, i));

        return sum;
    }

    int rot(int arr[], int idx) {

        int idx2 = arr.length - idx;
        int sum = 0;
        for (int i = 0; i < arr.length; i++) {
            if (idx2 == arr.length)
                idx2 = 0;

            sum += arr[i] * idx2;
            idx2++;
        }
        
        return sum;

    }
}

Was this solution helpful?