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:
 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.
 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)

Time Complexity : O(n)