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

Software Development
#1

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)