https://www.hackerrank.com/challenges/flatland-space-stations/problem
#include <stdio.h>
#define MAX 10000
int c[MAX];
void merge(int a[], int ,int ,int , int );
void mergesort(int a[], int ,int);
void mergesort(int a[],int low, int high)
{
int mid;
if(low<high)
{
mid=(low+high)/2;
mergesort(a,low,mid);
mergesort(a, mid+1,high);
merge(a,low,mid,mid+1,high);
}
}
/* merge two subparts obtained by dividing the array into 2 halves (low1 to high1 and low2 to high2)*/
void merge(int a[], int low1,int high1,int low2, int high2)
{
int i,j,k;
i=low1;
j=low2;
k=low1; /*after merging, lower index of merged array begins with low1,ends with high2*/
while(i<= high1 && j<=high2)
{
while(a[i]<=a[j] && i <=high1)
{
c[k++]=a[i++];
}
while(a[j]<a[i]&& j <= high2)
{
c[k++]=a[j++];
}
}
while(i<=high1) /* if i <= high1 means there are elements still in subpart1 (low1 to high1)*/
{
c[k++]=a[i++];
}
while(j<=high2)
{
c[k++]=a[j++];
}
for(k=low1;k<=high2;k++) /* the sorted sub array in 'c' is written back to original array 'a'*/
{
a[k]=c[k];
}
}
int main()
{
int n,m;
scanf("%d%d",&n,&m);
int a[m];
for(int i=0;i<m;i++)
scanf("%d",&a[i]);
mergesort(a,0,m-1);
int max=a[0];
for(int i=1;i<m;i++)
{
if(max<(a[i]-a[i-1])/2)
max=(a[i]-a[i-1])/2;
}
if(n-1-a[m-1] > max)
max=n-1-a[m-1];
printf("%d",max);
}
