Proof Needed for an algorithm

general
, ,
1

I was solving this problem. For that, I tried this code even though I had no proof of its correctness:

#include <iostream>
#include <cmath>
#include <algorithm>

using namespace std;

int main() {
    int animals;
    cin >> animals;
    
    int array[1000];
    
    for (int i = 0; i < animals; i++) {
        cin >> array[i];
    }
    
    sort(array, array + animals);
    
    int max_diff = 0;
    for (int i = 0; i < animals - 2; i++) {
        max_diff = max(max_diff, abs(array[i] - array[i+2]));
    }
    
    cout << max_diff;
    
    return 0;
}

But it still gave it an AC. What is basically does is sorts the array and find the maximum difference between two alternate animals. I want to get a proof for its correctness. Please help.

Thanks.

2

To achieve minimum difference the adjacent elements have to be as close as possible.

For this our general intuition is to sort the array, but there is a conflict that as it is circular the difference between the last and the first element will be high.

For example if you take the m=numbers 1, 2, 3, 4, 5, 6 the answer will be 5 because 6-1 = 5

The optimal solution is from a sorted array take elements at odd places in ascending order and then take elements at even places in descending order and then calculate the maximum difference.

For the array 1, 2, 3, 4, 5, 6 if you arrange them as per above explanation you will get
1, 3, 5, 6, 4, 2

so now the maximum difference will minimal i.e, 2 here.

The basic idea here is to cluster the elements in such a way to reduce the overall difference between the adjacent elements

This is not a perfect explanation, but I hope it gives the understanding

2 Likes