Maximize sum of consecutive differences in a circular array

Algorithm

This problem can be easily solved by greedy approach by ensuring that values with greater difference remains closer so that sum of differences becomes maximum and it can be done by placing largest and smallest consecutive.

Approach is given below:

1. Consider array is a1, a2, a3, a4,..., an.
2. After sorting array become b1, b2, b3, b4,..., bn.
3. Then arrangement b1, bn, b2, bn-1,..., bn/2, b(n/2)+1 gives the maximum sum of consecutive differences.  

Pseudocode

The pseudocode of given Problem is as follows:

1. Sort the given array A in non-decreasing order.
2. Declare an array S to store optimal arrangement. 
3. Initialise two pointers front and end pointing first and last element of sorted array respectively. 
4. Append two elements in array S pointed by pointers front and end and increase front by 1 and decrease end by 1. 
5. Repeat Step-4 untill front is not equal to end. 

Complexity

Time Complexity: ==**O(nlog(n))**==
Space Complexity: ==**O(n)**==

Implementation

   #include <bits/stdc++.h>
   using namespace std;
   int main()
   {
       int n, front, end, total, k=0;
       cin>> n;
       int A[n], S[n];
       for(int i=0; i< n; i++)
           cin>> A[i];
       sort(A, A+n);
       front= 0;end= n-1;
       while(front< end)
       {
           S[k]= A[front];
           k++;
           S[k]= A[end];
           k++; front++; end--;
       }
       if(front == end)
           S[k]= A[front];
       for(int i=0; i< n; i++)
       {
           cout<< S[i]<< " ";
           total= total + abs(S[i] - S[(i+1)%n]);
       }
       cout<< "\n"<< total;
       return 0;
   }
   

Application

Consider a situation in which N nodes of graph are given and each node has associated cost, find any N bidirectional edges joining these vertex such that final graph must be a strongly connected cyclic graph such that total value of graph is maximum, total value of graph is obtained by adding the absolute difference of cost of consecutive nodes of final cyclic graph in certain order(Either clockwise or anti-clockwise).

References

https://github.com/piyushmittal25/cosmos/tree/master/code/greedy_algorithms/src/Maximum%20Consecutive%20DIfference%20Sum