如：array={1,4,17,3,2,9} 最大值为：17-2=15
package datastruct.usearray; public class GetMaxOfTwoDiffer { //蛮力算法:时间复杂度为：o(n^2) private static void method(int array[]) { int n=array.length; int max=Integer.MIN_VALUE; for (int i = 0; i <n-1; i++) { for (int j = i+1; j < array.length; j++) { if (max<array[i]-array[j]) { max=array[i]-array[j]; } } } System.out.println("蛮力算法：两数最大的差值为："+max); } //利用动态规划:时间复杂度和空间复杂度均为：o(n) /** * 思路如下： * 1.申请两个额外空间，diff[] 和 max[] * diff[i]表示：以数组array的第i个元素作为减数的所有数对之差的最大值 * max[i]表示：前i+1个最大数，因为数组是从0开始，所以是前i+1个 * 2.由以上可知：求diff[i]的值分为两种情况： * 第一种是：diff[i-1] * 第二种是：max[i-1]-array[i] * 所以：diff[i]=max{diff[i-1],max[i-1]-array[i]} * max[i]=max{max[i-1],array[i]} */ private static int max(int a,int b) { return a>b?a:b; } private static void method2(int array[]) { if (array==null) { System.out.println("不存在！"); return ; } if (array.length<=1) { System.out.println("不存在！"); return; } int n=array.length; int diff[]=new int[n]; int max[]=new int[n]; //初始化 diff[0]=Integer.MIN_VALUE; max[0]=array[0]; for (int i = 1; i < n; i++) { diff[i]=max(diff[i-1],max[i-1]-array[i]); max[i]=max(max[i-1], array[i]); } System.out.println("动态规划：两数最大的差值为："+diff[n-1]); } //对动态规划的方法进行优化，进一步降低空间复杂度 /** * 由上述动态规划方法可知：我们只是用到了diff[i]和max[i],与其他无关 * 也就是说，我们可以用两个变量 diff max * diff替换掉diff[] * max替换掉max[] */ private static void method3(int array[]) { int n=array.length; if (array==null) { System.out.println("不存在！"); return; } if (n<=1) { System.out.println("不存在！"); return; } int max=array[0]; int diff=Integer.MIN_VALUE; for (int i = 1; i < n; i++) { diff=max(diff, max-array[i]); max=max(max, array[i]); } System.out.println("优化后动态规划：两数最大的差值为："+diff); } public static void main(String[] args) { int [] array={1,4,17,3,2,9}; method(array); method2(array); method3(array); } 运行结果如下：
