一，问题描述
给定一个正数数组arr（即数组元素全是正数），找出该数组中，两个元素相减的最大值，其中被减数的下标不小于减数的下标。
即求出： maxValue = max{arr[j]-arr[i] and j >= i}
二，求解思路
下面采用两种不同的算法来求解，第一种算法的时间复杂度为O(N)，第二种算法的时间复杂度为O(N^2)。
算法一思路如下：（初始时减数为arr[0]，然后算法不断记录比当前减数更小的减数）
maxValue初始化为0，因为当 i==j 时，arr[j] - arr[i] = 0，故 maxValue的值不可能为负数。
因此将下标 i 初始化为0，j 从下标1处开始向后扫描，并计算sub = arr[j]-arr[i]
若sub大于maxValue，则更新maxValue的值。
否则，若sub小于0，意味着找到一个新的数组元素，该数组元素比 arr[i]的值要小，则更新下标 i.
为什么这样可以？
因为：当计算 sub = arr[j]-arr[i]时，arr[i]越小，则得到的sub越大。而下标 i 不断标记更小的减数，后面的元素arr[j]与 更小的减数相减才能得到更大的差值。
比如，下图所示数组：
arr[0]=18，当j=2时，max=arr[2]-arr[0]=8。当遍历到arr[3]=12时，由于12小于18，故把下标 i 由 0 更新为 3。不需要”关注“下标为1和2的这两个元素。因为，
若在 j>3 后面有元素使得 arr[j]-arr[1] 或者 arr[j]-arr[2]>maxValue，则该arr[j]-arr[0]一定比 arr[j]-arr[1]更大，因为arr[1]和 arr[2]都比arr[0]大。
同理：也不需要关注元素值为12 和 元素值为10之间的元素，因为，若后面某个元素减去某个 “12 到 10之间的元素（16、18、22）”比maxValue大，那么它减去12一定更大。
这样，下标 i 记录的总是下一个比 arr[i] 更小的值（这有点类似于贪心算法的味道，每次总是贪比当前值更小的一个值），而不是如算法2中那样依次遍历数组中的每个元素。
代码如下：
1 //算法复杂度O(N). 找出数组arr中两个数相减的最大值 2 public static int maxValueOfSubtraction(int[] arr){ 3 int max = 0;// when j == i 4 int i = 0; 5 int sub; 6 for(int j = 1; j < arr.length; j++){ 7 sub = arr[j] - arr[i]; 8 if(sub > max) 9 max = sub; 10 else if(sub < 0)//means there is a number smaller than a[i](i initial value is 0) 11 i = j; 12 } 13 return max; 14 }
算法二：
就是一个很普通的方法。求出 数组中所有下标大的元素减去下标小的元素，找出其中的最大值即可。代码如下：
1 //O(N^2) 找出数组arr中两个数相减的最大值 2 public static int maxValueSub(int[] arr){ 3 int max = 0; 4 int sub; 5 for(int i = 0; i < arr.length; i++){ 6 for(int j = i+1; j < arr.length; j++){ 7 sub = arr[j] - arr[i]; 8 if(sub > max) 9 max = sub; 10 } 11 } 12 return max; 13 }
一个错误的解法：
由于题目中要求的是 被减数的下标要大于减数的下标，故下面解法是错误的：
依次扫描数组中的每个元素，找出数组元素中的最大值和最小值。最大值减去最小值 即为两个元素相减的最大值。
错误的原因是：最大值元素的下标 可能 比 最小值元素的下标要小。
错误解法代码如下：
1 public static int maxValueSub3(int[] arr){ 2 int min, max; 3 int indexM = -1;int indexm = -1; 4 min = max = arr[0]; 5 for(int i = 1; i < arr.length; i++){ 6 if(arr[i] > max) 7 { 8 max = arr[i]; 9 indexM = i; 10 } 11 else if(arr[i] < min){ 12 min = arr[i]; 13 indexm = i; 14 } 15 } 16 System.out.println("indexM" + indexM + " indexm:" + indexm); 17 return max - min; 18 }
三，运行时间的比较
采用 这篇文章 中提到的随机数生成算法 来随机生成一个数组，然后比较上面两个算法的运行时间。
机器环境如下：
OS:win7 64bit、RAM:6GB、CPU:Pentium(R)Dual-Core E5800@3.2GHz
时间比较如下：
数组大小 算法1运行时间 算法2运行时间
100*100 1 61
200*100 3 158
400*100 2 568
500*100 2 878
100*100*10 4 3451
整个代码如下：
1 /* 2 * given an array, find out the max value of two numbers's distraction. 3 * max{a[j]-a[i]} under the condition of j>=i 4 */ 5 public class MaxValue { 6 7 //算法复杂度O(N). 找出数组arr中两个数相减的最大值 8 public static int maxValueOfSubtraction(int[] arr){ 9 int max = 0;// when j == i 10 int i = 0; 11 int sub; 12 for(int j = 1; j < arr.length; j++){ 13 sub = arr[j] - arr[i]; 14 if(sub > max) 15 max = sub; 16 else if(sub < 0)//means there is a number smaller than a[i](i initial value is 0) 17 i = j; 18 } 19 return max; 20 } 21 22 //O(N^2) 找出数组arr中两个数相减的最大值 23 public static int maxValueSub(int[] arr){ 24 int max = 0; 25 int sub; 26 for(int i = 0; i < arr.length; i++){ 27 for(int j = i+1; j < arr.length; j++){ 28 sub = arr[j] - arr[i]; 29 if(sub > max) 30 max = sub; 31 } 32 } 33 return max; 34 } 35 36 37 public static void main(String[] args) { 38 int[] arr = C2_2_8.algorithm3(100*100*10); 39 40 long start = System.currentTimeMillis(); 41 int r = maxValueOfSubtraction(arr); 42 long end = System.currentTimeMillis(); 43 System.out.println("maxValue=" + r + " O(N)'s time:" + (end -start)); 44 45 long start2 = System.currentTimeMillis(); 46 int r2 = maxValueSub(arr); 47 long end2 = System.currentTimeMillis(); 48 System.out.println("maxValue=" + r2 + " O(N^2)'s time:" + (end2 - start2)); 49 } 50 }
