庆祝61

//这个很简单啊！怎么样身高差最小呢？就是两身高差不多的人站一起咯，小时候站队 老师总让
//矮的站中间高的站两边，就是这个道理，如 9 8 7 6 6 7 8 9然后9和9再拉手不就可以了吗 ！所以
//将数据输入一个数组如【8 9 7 6 5 4 3 2】然后排序【2 3 4 5 6 7 8 9】然后遍历数组进入
//一个队列一个栈 现规定，索引为0,2,4，，，的依次进入队列Q1，索引为1,3,5，，，，的依次进入//栈S1，就形成一个队列2 4 6 8 （队列尾为8）和一个栈3 5 7 9（栈顶为9） 。然后出栈9 7 5 3 
//依次进入队列尾 形成 2 4 6 8 9 7 5 3 就排队成功，2和3拉手就成圈，求每个元素与挨着的
//距离就可以了

所以答案是在如下几项中最大值(已排序):

#include<bits/stdc++.h>
using namespace std;
int main(){
	int n;
	cin >> n;
	vector<int> h(n);
	for (int i = 0; i<n; i++){
		cin >> h[i];
	}

	sort(h.begin(), h.end());

	int a = h[1] - h[0];
	int b = h[n - 1] - h[n - 2];
	int maxVal = max(a, b);
	for (int i = 0; i<n - 2; i++){
		int c = h[i + 2] - h[i];
		maxVal = max(maxVal, c);
	}
        cout<<maxVal;
	return 0;
}

//要想小朋友的身高差尽量小，在升序排好队后，应该让小朋友错位排队

//举例来说，如果有5个小朋友，1 2 3 4 5，首先肯定要避免1与5在一起，所以4和3要插在1与5之间

//那么2是放在4与1之间呢，还是3与1之间呢？

//如图，因为4与1的差肯定大于4与2或3与1的差，所以2肯定要排在1与4之间

   vs  

import java.util.Arrays; 

	import java.util.Scanner;



	





	public class Main { 



	





	 public static void main(String[] args){



	  Scanner in=new Scanner(System.in);



	  int n=in.nextInt();



	  int[] h=new int[n];



	   



	  for(int i=0;i<n;i++){



	   h[i]=in.nextInt();



	  }



	   



	  Arrays.sort(h);



	   



	  int max=Math.max(h[1]-h[0],h[n-1]-h[n-2]);



	  for(int i=0;i<n-2;i++){



	   max=Math.max(max, h[i+2]-h[i]);



	  }



	   



	  System.out.println(max);



	 }



	}

}

// 思路： 先把所有的身高从大到小排列，分别为0-(n-1)，则最大值(n-1)左右分别为(n-2)和(n-3)
//        即....（n-4）、(n-2)、(n-1)、（n-3）、（n-5）...   然后最小的两个值围成一圈

import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;


public class Main {
	public static void main(String[] args){
		Scanner in = new Scanner(System.in);
        while (in.hasNextInt()) {//注意while处理多个case
        	int num = in.nextInt();
        	ArrayList<Integer> heights = new ArrayList<Integer>();
        	for(int i=0;i<num;i++){
        		heights.add(in.nextInt());
        	}
        	Collections.sort(heights);
        	int max = -1;
        	// 倒数第一大
        	int cha = Math.abs(heights.get(num-1)-heights.get(num-2));
        	int tmp = num-2;
            while(tmp>1){
            	cha = Math.abs(heights.get(tmp)-heights.get(tmp-2));
            	if(cha>max)
            		max = cha;
            	tmp = tmp-2;
            }
            tmp = num-1;
            while(tmp>1){
            	cha = Math.abs(heights.get(tmp)-heights.get(tmp-2));
            	if(cha>max)
            		max = cha;
            	tmp = tmp-2;
            }
            cha = Math.abs(heights.get(0)-heights.get(1));
        	if(cha>max)
        		max = cha;
        	System.out.print(max);
        }
	}
}

import java.util.*;

public class Main{
	public static void main(String[] agrs) {
		Scanner input = new Scanner(System.in);
		int len = input.nextInt();
		input.nextLine();
		int[] nums = new int[len];
		for(int i = 0; i < len; i++) {
			nums[i] = input.nextInt();
		}
		Arrays.sort(nums);
		int pre = nums[1] - nums[0];
		int maxDiff = 0;
		for(int i = 2; i < len; i++) {
			int cur = nums[i] - nums[i-1];
			if(cur + pre > maxDiff) maxDiff = cur + pre;
			pre = cur;
		}
		System.out.println(maxDiff);
	}
}

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.Arrays;
public class Main{
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int size = Integer.parseInt(br.readLine());
        String height = br.readLine();
        String[] hs = height.split(" ");
        int[] heights = new int[size];
        for(int i = 0; i < heights.length; i++){
            heights[i] = Integer.parseInt(hs[i]);
        }
        System.out.println(handle(heights));
    }
    private static int handle(int[] heights){
        Arrays.sort(heights);
        int max = heights[2] - heights[0];
        for(int i = 2; i < heights.length; i++){
            int gap = heights[i] - heights[i - 2];
            if(gap > max){
                max = gap;
            }
        }
        return max;
    }
}

import java.math.BigInteger;
import java.util.Arrays;
import java.util.Scanner;

//System.out.println("");


public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int d=0;
        int dm=0;
        int n = sc.nextInt();
        int[] array = new int[n];
        for(int i=0; i<n; i++){
            array[i] = sc.nextInt();
        }
        Arrays.sort(array);//身高排序
       for(int i=2;i<n;i+=2){
           d=array[i]-array[i-2];
           if(d<0)d=-d;
           if(d>=dm)dm=d;
            
       }//dm为第一列最大身高差
       for(int i=3;i<n;i+=2){
           d=array[i]-array[i-2];
           if(d<0)d=-d;
           if(d>=dm)dm=d;
           
           
           
       }//dm为第一列和第二列 最大身高差 d=array[0]-array[1]; 
if(d<0)d=-d;
if(d>=dm)dm=d;
d=array[n-1]-array[n-2]; 
if(d<0)d=-d;
if(d>=dm)dm=d;
//dm为第一列、第二列 、列连接处    最大身高差 System.out.println(dm);
        
    }
}

	思路：假如h1 h2 h3 h4 h5 h6 ..hn  依次递增（排序）



	h1   h2



	h3   h4



	h5   h6



	...



	hn-1 hn



	



	这样形成的圈可以保证身高差的最大值最小。 依次计算 身高差 d  取最大值即可

import java.util.*;
public class Main{
	public static void main(String[] args) {
		// TODO Auto-generated method stub
       Scanner sc=new Scanner(System.in);
       while(sc.hasNext()){
          int n=sc.nextInt();    //小朋友个数;
          int array[]=new int[n];
          int i=0;
          int maxCount=0;
          ArrayList <Integer> list=new ArrayList <Integer>();
          while(i<n){
        	  array[i]=sc.nextInt();
        	  i++;
          }      
         Arrays.sort(array);
        	for(int j=0;j<array.length;j++){
        		if(j%2==0){
        			list.add(array[j]);
        		}
        	}
        	for(int jj=array.length-1;jj>0;jj--){
        		if(jj%2!=0){
        			list.add(array[jj]);
        		}
        	}
         int arr[]=new int[list.size()];
         Iterator <Integer>it=list.iterator();
         int index=0;
         while(it.hasNext()){
        	 arr[index]=it.next();
        	 index++;
         }
    	maxCount=Math.abs(arr[arr.length-1]-arr[0]);  
    	  for(int k=1;k<arr.length;k++){
               int temp=Math.abs(arr[k]-arr[k-1]);
               maxCount=(maxCount>temp)?maxCount:temp;
          }
    	  System.out.println(maxCount);

       }
       sc.close();
	}
}

import  java.util.*;
public class Celebrate61 {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
 int n = scanner.nextInt();
 int[] arr = new int[n];
 for (int i = 0; i ; i++) {
arr[i] = scanner.nextInt();
  }
Arrays.sort(arr); //先对数组进行排序
 //用LinkedList来实现队列的先进先出功能  LinkedList queue = new LinkedList();
  Stack stack = new Stack();
 for (int i = 0; i ; i++) {
if((i&1) == 0) {
queue.addLast(arr[i]);
  }
else stack.push(arr[i]);
  }
int size = stack.size();
 for(int i = 0; i ; i++) {
queue.addLast(stack.pop());
  }
int max = Integer.MIN_VALUE;
 for (int i = 1; i ; i++) {
int inter = 0;
 if(i == 0) {
inter = Math.abs(queue.get(n-1) - queue.get(0));
  }
else {
inter = Math.abs(queue.get(i) - queue.get(i-1));
  }
if(max < inter) {
max = inter;
  }
}
System.out.println(max);
  }
}

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main(int argc, char const *argv[])
{
	int n;
	cin>>n;
	vector<int> height(n,0);
	for (int i = 0; i < n; ++i)
	{
		cin>>height[i];
	}
	sort(height.begin(),height.end());
	vector<int> res(n,0);
	auto itb=res.begin();
	auto ite=res.end();
	ite--;
	for(int i=0;i<n;i=i+2){
		if(ite==itb){
			*ite=height[i];
			break;
		}
		*itb=height[i];
		*ite=height[i+1];
		ite--;
		itb++;
	}
	int maxh=abs( res[0]- res[1]);
	for(int i=2;i<n;i++){
		maxh=max(maxh,abs( res[i]- res[i-1]));
	}
	cout<<max(maxh,abs( res[0]- res[n-1]));
	return 0;
}

1.将数组排序，如：105 103 100 98  2.排好的数组分为两组：arr1{105,100} arr2{98,103}
3.连接成新数组：105,100,98,103
4.求最大的差值

while(n=readline()){
    var arr=readline().split(' ');   
    var allVal=[];
    var arr1=[],arr2=[];
    arr=arr.sort(function(a,b){
        return b-a;
    })
    
    for(var i=0; i<n; i++){
        if(i%2==0) arr1.push(arr[i]);
        else arr2.unshift(arr[i]);
    }
    var res=arr1.concat(arr2);
    
    allVal.push(Math.abs(res[0]-res[n-1]));
    for(var i=1; i<n; i++){
        allVal.push(Math.abs(res[i]-res[i-1]));
    }
    allVal=allVal.sort(function(a,b){
        return b-a;
    })
    print(allVal[0]);
}

#排序后以最小值为中心，左边加一个第二小的值，右边家一个第三小的值
#最后计算身高差最大值
def f(n, h_i):
    h_i.sort(reverse = True)
    team = [h_i.pop()]
    n -= 1
    while n > 0:
        team.append(h_i.pop())
        n -= 1
        if n > 0:
            team.insert(0, h_i.pop())
            n -= 1
    ret = []
    for i in range(len(team)-1):
        ret.append(abs(team[i]-team[i+1]))
    return max(ret)
if __name__ == '__main__':
    while 1:
        try:
            n = input()
            h_i = map(int, raw_input().split())
        except:
            break
        print f(n, h_i)