### Maximize sum of consecutive differences in a circular array

Reading time: 16 minutes | Coding time: 5 minutes

Given an array A with values ** a_{1}, a_{2}, a_{3}, a_{4},..., a_{n}**. 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

**then maximize**

*b*_{1}, b_{2}, b_{3}, b_{4},..., b_{n}`|`*b*_{1}-b_{2}| + |*b*_{2}-b_{3}| + |*b*_{3}-b_{4}| + ..... + |*b*_{n-1}-b_{n}| + |*b*_{n}-b_{1}|

*.*

*
*

Space Complexity: ==**O(n)**==
### 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 a_{1}, a_{2}, a_{3}, a_{4},..., a_{n}. 2. After sorting array become b_{1}, b_{2}, b_{3}, b_{4},..., b_{n}. 3. Then arrangement b_{1}, b_{n}, b_{2}, b_{n-1},..., b_{n/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`

andfrontpointing first and last element of sorted array respectively.end`4. Append two elements in array S pointed by pointers`

andfrontand increaseendby 1 and decreasefrontby 1.end`5. Repeat Step-4 untill`

is not equal tofront.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