NUHMAN.com

📘 Problem Statement

Given an array of integers nums, return the maximum possible sum of i * nums[i], where i is the index of the array and the array is rotated.

You can rotate the array to the right by any number of positions, and you need to determine the maximum sum possible for all such rotations.

• The problem can be interpreted as maximizing the sum of products of the array’s indices and its elements after performing multiple rotations.

📚 Example:

python

Input:
nums = [4, 3, 2, 6]
Output:
26
Explanation: 
Here, we perform the following steps:
- Initially, the sum is `0 * 4 + 1 * 3 + 2 * 2 + 3 * 6 = 0 + 3 + 4 + 18 = 25`
- After rotating the array once to the right: `[6, 4, 3, 2]`
  The sum becomes: `0 * 6 + 1 * 4 + 2 * 3 + 3 * 2 = 0 + 4 + 6 + 6 = 16`
- After rotating the array again to the right: `[2, 6, 4, 3]`
  The sum becomes: `0 * 2 + 1 * 6 + 2 * 4 + 3 * 3 = 0 + 6 + 8 + 9 = 23`
- After rotating the array again to the right: `[3, 2, 6, 4]`
  The sum becomes: `0 * 3 + 1 * 2 + 2 * 6 + 3 * 4 = 0 + 2 + 12 + 12 = 26`
Thus, the maximum sum is `26`.

🧠 Key Insight

Instead of rotating the array multiple times and calculating the sum for each rotation (which would be inefficient), we can use a more optimized approach that computes the sum iteratively:

• The key observation is that if we know the sum for one rotation, we can derive the sum for the next rotation using the previous sum and the properties of the array.
• The idea is that the sum of each rotation is related to the sum of the previous one, and we can compute each subsequent sum in constant time by adjusting the previous sum.

💡 Approach

1. Initial Sum Calculation:

• First, calculate the sum for the initial array where no rotations are performed.

1. Sum Relation:

• Once we have the sum for the initial array, each subsequent sum can be computed using the following formula:
• S(i) = S(i-1) + sum(nums) - len(nums) * nums[len(nums)-i]
• This formula derives from the observation that each element is being shifted and contributes differently to the sum in each rotation.

1. Optimization:

• Instead of calculating the sum for each rotation from scratch, we can iteratively calculate the next sum from the previous sum using the above formula.

1. Iterate and Find Maximum:

• After calculating the sum for the initial array, use the iterative formula to calculate the sum for each rotation and keep track of the maximum sum.

🐍 Python Code

python

class Solution:
    def maxRotateFunction(self, nums: list[int]) -> int:
        n = len(nums)
        if n == 0:
            return 0

        # Calculate the sum of the array and the sum of i * nums[i] for the initial array
        total_sum = sum(nums)
        current_sum = sum(i * num for i, num in enumerate(nums))
        max_sum = current_sum

        # Iterate to calculate the sum for each rotation and keep track of the maximum
        for i in range(1, n):
            current_sum += total_sum - n * nums[-i]
            max_sum = max(max_sum, current_sum)

        return max_sum

🔍 Step-by-Step Explanation

1. Initial Sum Calculation:

python

total_sum = sum(nums)
current_sum = sum(i * num for i, num in enumerate(nums))

• total_sum: The sum of all elements in the array. This helps us to efficiently compute the sum of subsequent rotations.
• current_sum: The sum of i * nums[i] for the initial array (no rotations).

2. Iterate to Compute the Next Rotation’s Sum:

python

for i in range(1, n):
    current_sum += total_sum - n * nums[-i]
    max_sum = max(max_sum, current_sum)

• For each rotation, we adjust the current_sum using the formula:
• S(i) = S(i-1) + total_sum - n * nums[len(nums)-i]
• This formula avoids re-calculating the sum for every rotation from scratch, optimizing the process.

3. Return the Maximum Sum:

python

return max_sum

• After iterating through all possible rotations, we return the maximum sum encountered.

💡 Example Walkthrough

Example 1:

python

Input:
nums = [4, 3, 2, 6]
Output:
26

1. Initial Calculation:

• total_sum = 4 + 3 + 2 + 6 = 15
• current_sum = 0 * 4 + 1 * 3 + 2 * 2 + 3 * 6 = 0 + 3 + 4 + 18 = 25
• Set max_sum = 25.

1. First Rotation ([6, 4, 3, 2]):

• current_sum = 25 + 15 - 4 * 2 = 25 + 15 - 8 = 32
• max_sum = max(25, 32) = 32.

1. Second Rotation ([2, 6, 4, 3]):

• current_sum = 32 + 15 - 4 * 3 = 32 + 15 - 12 = 35
• max_sum = max(32, 35) = 35.

1. Third Rotation ([3, 2, 6, 4]):

• current_sum = 35 + 15 - 4 * 4 = 35 + 15 - 16 = 34
• max_sum = max(35, 34) = 35.

1. Final Output: 35

⏱️ Time & Space Complexity

MetricComplexityTime ComplexityO(n)Space ComplexityO(1)

• Time Complexity:
• We loop through the array once to compute the initial sum, and then we perform n-1 iterations to compute each subsequent rotation's sum, making the overall time complexity O(n), where n is the length of the array.
• Space Complexity:
• We only use a few variables (total_sum, current_sum, max_sum), so the space complexity is O(1).

🧵 Final Thoughts

LeetCode 396 is a classic example of leveraging the mathematical properties of the problem to optimize the solution. By understanding the relationship between consecutive rotations, we avoid recalculating the sum from scratch every time, thus achieving an efficient solution with a time complexity of O(n). This problem is a great way to practice optimization and efficient use of iterative relations.