【答案解析】问题描述：数组中的一个数字减去它右边子数组中的一个数字可以得到一个差值，求所有可能的差值中的最大值，例如，数组{1，4，17，3，2，9}中，最大的差值为17-2=15。
方法一：“蛮力”法。“蛮力”法也是最容易想到的方法，其原理如下：首先，遍历数组，找到所有可能的差值；其次，从所有差值中找出最大值。具体实现方法为：针对数组a中的每个元素a[i](0＜i＜n-1)，求所有a[i]-a[j](i＜j＜n)的值中的最大值。示例如下：
public class Test{
public static int getMax(int[]a){
if(a==null)
return Integer.MIN_VALUE;
int len=a.length;
if(len＜=1)
return Integer.MIN_VALUE;
int max=Integer.MIN_VALUE;
for(int i=0; i＜len-1; i++){
tbr(int j=i+1; j＜len; j++)
if(a[i]-a[j]＞max)
max=a[i]-a[j];
}
return max;
}
public static void main(String[]args){
int[]a={1, 4, 17, 3, 2, 9};
System.out.println(getMax(a));
}
}
程序运行结果为：
15
采用这种方法虽然也能求出最大值，但是它的时间复杂度为O(n)。
方法二：二分法。通过二分法可以减少计算的次数。思路如下：把数组分为两个子数组，那么最大的差值只能有3种可能：①最大的差值对应的被减数和减数都在左子数组中，假设最大差值为leftMax；②被减数和减数都在右子数组中，假设最大差值为rightMax；③被减数是左子数组的最大值，减数是右子数组中的最小值，假设差值为mixMax。那么就可以得到这个数组的最大差值为这3个差值的最大值，即max(leftMax，rightNax，mixMax)。实现代码如下：
import java util.concurrent.atomic.AtomicInteger;
public class Test {
public static int getMax(int a[]){
if(a==null)
return Integer.MIN_VALUE;
int len=a.length;
if(len＜=1)
return Integer.MIN_VALUE;
AtomicIntegermax=new AtomicInteger(0);
AtomicIntegermin=new AtomicInteger(0);
return getMaxDiff(a, 0, len-1, max, min);
}
public static int getMaxDiff(int a[], int begin, int end, AtomicInteger max, AtomicInteger min){
if(begin==end){
max.set(a[begin]);
min.set(a[begin]);
return Integer.MIN_VALUE;
}
int middle=begin+(end-begin)/2;
//数组前半部分的最小值与最大值
AtomicIntegerlMax=new AtomicInteger(0);
AtomicIntegerlMin=new AtomicInteger(0);
//数组前半部分的最：赶差值(第一种情况)
int leflMax=getMaxDiff(a, begin, middle, 1Max, 1Min);
//数组后半部分的最小值与最大值
AtomicIntegerrMax=new AtomicInteger(0);
AtomicIntegerrMin=new AtomicInteger(0);
//数组后半部分的最大差值(第二种情况)
int rightMax=getMaxDiff(a, middle+1, end, rMax, rMin);
//对应第三种情况
int mixMax=1Max.get()-rMin.get();
//求数组的最大值与最小值
if(1Max.get()＞rMax.get())
max.set(1Max.get());
else
max.set(rMax.get());
if(1Min.get()＜rMin.get())
min.set(1Min.get());
else
min.set(rMin.get());
//求最大的差值
int allMax=(leftMax＞rightMax)?leftMax:rightMax;
allMax=(allMax＞mixMax)?allMax:mixMax;
return allMax;
}
public static void main(String[]args){
int[]a={1, 4, 17, 3, 2, 9};
System.out.println(getMax(a));
}
}
程序运行结果为：
15
显然，以上这种方法对数组只经过一次遍历，一次时间复杂度为O(n)，但是由于采用了递归的实现方式，在递归调用时要进行压栈与弹栈操作，因此有额外的开销，会导致算法性能有所下降。另外，在实现时，为了通过传递引用的方式获取数组的最大值与最小值，使用了AtomicInteger而不是Integer类。主要原因为Integer类虽然也可以传递引用，但是它是不可变量，在方法内部不能对其进行修改。
方法三：动态规划。通过对题目进行分析，发现这是一个非常典型的动态规划问题，可以用动态规划的方法来求解。实现思路如下：给定数组a，申请额外的数组diff和max，其中diff[i]是以数组中第i个数字为减数的所有数对之差的最大值(前i+1个数组成的子数组中最大的差值)，max[i]为前i+1个数的最大值。假设已经求得了diff[i]，diff[i+1]的值有两种可能性：①等于diff[i]；②等于max[i]-a[i]。通过上面的分析，可以得到动态规划方法的计算表达式为：diff[i+1]=max(diff[i]，max[i-1]-a[i])，max[i+1]=max(max[i]，a[i+1])。数组最大的差值为diff[n-1](n为数组的长度)。示例如下：
public class Test{
public static int max(int m, int n){
return(m＞n)?m:n;
}
public static int getMax(int[]a){
if(a==null)
return Integer.MIN_VALUE;
int len=a.length;
if(len＜=1)
return Integer.MIN_VALUE;
int[]diff=New int[len];
int[]max=new int[len];
diff[0]=0;
max[0]=a[0];
for(int i=1; i＜len; i++){
diff[i]=max(diff[i-1], max[i-1]-a[i]);
max[i]=max(max[i-1], a[i]);
}
return diff[len-1];
}
public static void main(String[]args){
int[]a={1, 4, 17, 3, 2, 9};
System.out.println(getMax(a));
}
}
程序运行结果为：
15
以上这种方法也是对数据进行了一次遍历，因此时间复杂度为O(n)，由于没有采用递归的方式，因此相比方法二，在性能上有所提升。由于引入了两个额外的数组，因此这个算法的空间复杂度也为O(n)。
从动态规划方法的计算公式中可以看出，在求解diff[i+1]时，只用到了diff[i]与max[i]，而与数组diff和max中其他数字无关，因此可以通过两个变量而不是数组来记录diff[i]与max[i]的值，从而降低了算法的空间复杂度。示例如下：
public class Test{
public static int max(int m, int n){
return(m＞n)?m:n;
}
public static int getMax(int[]a){
if(a==null)
return Integer.MIN_VALUE;
int len=a.length;
if(len＜=1)
return Integer.MIN_VALUE;
int diff=0;
int max=a[0];
for(int i=1; i＜len; i++){
diff=max(diff, max-a[i]);
max=max(max, a[i]);
}
return diff;
}
public static void main(String[]args){
int[]a={1, 4, 17, 3, 2, 9};
System.out.println(getMax(a));
}
}
引申：这道题还可以用求最大子数组之和的方法来解决吗?
答案：可以。实现思路如下：给定一个数组a(数组长度为n)，额外申请一个长度为n-1的数组diff，数组diff中的值满足diff[i]=a[i]-a[i+1]，那么a[i]-a[j](0＜i＜j＜n)就等价于diff[i]+diff[i+1]+…+diff[j]。因此，求所有a[i]-a[j]组合的最大值就可以转换为求解所有diff[i]+diff[i+1]+…+diff[j]组合的最大值。由于diff[i]+diff[i+1]+…+diff[j]代表diff的一个子数组，因此可以用11.5.3节中求最大子数组之和的方法来解决。