# Maximum sum of i*arr[i] Method - 3

Method 3: The method discusses the solution using pivot in O(n) time. The pivot method can only be used in the case of a sorted or a rotated sorted array. For example: {1, 2, 3, 4} or {2, 3, 4, 1}, {3, 4, 1, 2} etc.

• Approach: Let’s assume the case of a sorted array. As we know for an array the maximum sum will be when the array is sorted in ascending order. In case of a sorted rotated array, we can rotate the array to make it in ascending order. So, in this case, the pivot element is needed to be found following which the maximum sum can be calculated.
• Algorithm:
1. Find the pivot of the array : if arr[i] > arr[(i+1)%n] then it is the pivot element. (i+1)%n is used to check for the last and first element.
2. After getting pivot the sum can be calculated by finding the difference with the pivot which will be the multiplier and multiply it with the current element while calculating the sum
• Implementations:
• C++

`// C++ program to find maximum sum of all`

`// rotation of i*arr[i] using pivot.`

`#include <iostream>`

`using` `namespace` `std;`

`// fun declaration`

`int` `maxSum(` `int` `arr[], ` `int` `n);`

`int` `findPivot(` `int` `arr[], ` `int` `n);`

`// function definition`

`int` `maxSum(` `int` `arr[], ` `int` `n)`

`{`

`` `int` `sum = 0;`

`` `int` `i;`

`` `int` `pivot = findPivot(arr, n);`

`` `// difference in pivot and index of`

`` `// last element of array`

`` `int` `diff = n - 1 - pivot;`

`` `for` `(i = 0; i < n; i++)`

`` `{`

`` `sum = sum + ((i + diff) % n) * arr[i];`

`` `}`

`` `return` `sum;`

`}`

`// function to find pivot`

`int` `findPivot(` `int` `arr[], ` `int` `n)`

`{`

`` `int` `i;`

`` `for` `(i = 0; i < n; i++)`

`` `{`

`` `if` `(arr[i] > arr[(i + 1) % n])`

`` `return` `i;`

`` `}`

`}`

`// Driver code`

`int` `main(` `void` `)`

`{`

``

`` `// rotated input array`

`` `int` `arr[] = {8, 3, 1, 2};`

`` `int` `n = ` `sizeof` `(arr) / ` `sizeof` `(` `int` `);`

`` `int` `max = maxSum(arr, n);`

`` `cout << max;`

`` `return` `0;`

`}`

Output:

29

• Complexity analysis:
• Time Complexity : O(n)
As only one loop was needed to traverse from 0 to n to find the pivot. To find the sum another loop was needed, so the complexity remains O(n) .
• Auxiliary Space : O(1).
We do not require extra space to so the Auxiliary space is O(1)