Maximize sum of consecutive differences in a circular array

Reading time: 16 minutes | Coding time: 5 minutes

Given an array A with values   a1, a2, a3, a4,..., an. Now, arrange all elements of array A such that sum of absolute differences of consecutive elements is maximum, i.e consider after an arrangement the array is b1, b2, b3, b4,..., bn then maximize |b1-b2| + |b2-b3| + |b3-b4| + ..... + |bn-1-bn| + |bn-b1|.


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.  


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. 


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


   #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];
           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;


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