Home » Data Structure » Array Data Structure

Find maximum value of Sum( i*array[i] ) with only rotations on given array allowed

C++ implementation to find the maximum value of Sum( i*array[i] ) with only rotations on given array allowed.
Submitted by Vikneshwar GK, on February 20, 2022

Consider an integer array of size n. The constraint is that only rotation operation can be performed on the array. The task at hand is to find the maximum sum of i*array[i] by performing rotation operation.

Example

Input:
array[]= {5, 1, 2, 3, 4}
            
Output:
Maximum Value: 40

Explanation:
After one rotation, array becomes {1, 2, 3, 4, 5}
0*1 + 1*2 + 2*3 + 3*4 + 4*5 = 40


Input:
array[]= {50, 10, 20, 30, 40}

Output:
Maximum Value: 400

Solution:

This is an efficient approach that involves calculating one solution from the previous solution, i.e., if Sj is the sum of i*array[i] with j rotations, then we can calculate Sj+1 using Sj and Sj-1. It can be calculated using the following formula:

Sj - Sj-1 = arraySum - n * array[n - j]

Where arraySum is the sum is array[i], n is the length of the array, j is the rotation number.

• Iterate through the array and calculate arraySum
• Calculate S0 by performing i*array[i] for the array
• Use the above-mentioned formula to calculate the next solutions
• Return the solution that has the maximum value

C++ Implementation

#include <iostream>
using namespace std;

// Function to return maximum value of
// i*array[i]
int maxSum(int array[], int length)
{

    int arraySum = 0;
    int currVal = 0;
    for (int i = 0; i < length; i++) {
        arraySum = arraySum + array[i];
        currVal = currVal + (i * array[i]);
    }

    // Initialize maxVal with currVal
    int maxVal = currVal;

    // find other solution using the formula
    for (int j = 1; j < length; j++) {
        currVal = currVal + arraySum - length * array[length - j];
        if (currVal > maxVal)
            maxVal = currVal;
    }

    // Return result
    return maxVal;
}

// Main function
int main()
{
    int array[100], N, element;
    
    cout << "Enter Number of elements: ";
    cin >> N;

    for (int i = 0; i < N; i++) {
        cout << "Enter element " << i + 1 << ":";
        cin >> array[i];
    }
    cout << "Maximum Value: " << maxSum(array, N);

    return 0;
}

Output:

Enter Number of elements: 5
Enter element 1:5
Enter element 2:1
Enter element 3:2
Enter element 4:3
Enter element 5:4
Maximum Value: 40

Time Complexity: O(n), where n is the length of the array.