1 public class MaxSub 2 { 3     public static void main(String[] args) 4     { 5         int[] a ={5,7,3,1,6,2}; 6         System.out.println(maxSub(a)); 7  8     } 9     10     /**11      * @用于找出N个随机数在数轴相邻位置的最大差值12      */13     public static int maxSub(int[] a)14     {15        int min=a[0];//初始化数组的最小值min16        int max=a[0];//初始化数组的最大值max17     for (int i = 0; i < a.length; i++)//循环一次找出数轴最大最小值复杂度O（N）18     {19        if (a[i] < min)20          min = a[i];21        if (a[i] > max)22          max = a[i];23     }24     int[] count = new int[max-min+1];//记录数轴上位置的数组，从min开始到max结束25     for (int i = 0; i< max-min+1; i++)//初始化坐标轴数组  复杂度为O（max-min+1）和N线性关系26     {27        count[i] = 0;28     }29     for(int i = 0;i< a.length; i++)//标记数组a在数轴上位置  复杂度为O（N）30     {31      count[a[i]-min]++;32     } 33     int maxSub = 0;//最大差值34     int tempSub = 1;//数轴上相邻两个数的距离35     for(int i = 0;i< max-min+1; i++)//根据坐标轴上标记位置找出相邻最大差值maxSub 复杂度为O（max-min+1）36     {37       if (count[i]==0)tempSub++;38       else{39            if(tempSub>maxSub)40              {41               maxSub = tempSub;42              }43              tempSub = 1;44             }45      }46     return maxSub;47     }48 }

思路：

 复杂度为N找出最大值最小值，然后建立一个长度为最大值减去最小值加1的数组作为坐标轴。

 先初始化数组，数组每一项都为0，然后把原数组遍历， 对count[a[i]-min]++;相当于标记数组在坐标轴上位置，

最后找到相邻非零元素间最远距离即为最大差值