java-61-在数组中，数字减去它右边(注意是右边)的数字得到一个数对之差. 求所有数对之差的最大值。例如在数组{2, 4, 1, 16, 7, 5,
思路来自：http://zhedahht.blog.163.com/blog/static/2541117420116135376632/
写了个java版的

public class GreatestLeftRightDiff {/** * Q61.在数组中，数字减去它右边(注意是右边)的数字得到一个数对之差。 * 求所有数对之差的最大值。例如在数组{2, 4, 1, 16, 7, 5, 11, 9}中，数对之差的最大值是11，是16减去5的结果。 */public static void main(String[] args) {int[] a={2, 4, 1, 16, 7, 5, 11, 9};int result=greatestLeftRightDiff01(a);System.out.println(result);result=greatestLeftRightDiff02(a);System.out.println(result);}/*引用原文： * 如果输入一个长度为n的数组numbers，我们先构建一个长度为n-1的辅助数组diff， * 并且diff[i]等于numbers[i]-numbers[i+1]（0<=i<n-1）。 * 如果我们从数组diff中的第i个数字一直累加到第j个数字（j > i）， * 也就是diff[i] + diff[i+1] + … + diff[j]  * = (numbers[i]-numbers[i+1]) + (numbers[i + 1]-numbers[i+2]) + ... + (numbers[j]  numbers[j + 1]) *  = numbers[i]  numbers[j + 1]。 *  分析到这里，我们发现原始数组中最大的数对之差（即numbers[i]  numbers[j + 1]） *  其实是辅助数组diff中最大的连续子数组之和。 */public static int greatestLeftRightDiff01(int[] a){if(a==null||a.length<2){return Integer.MIN_VALUE;//min=1<<31}int len=a.length;int[] diff=new int[len-1];for(int i=1;i<len;i++){diff[i-1]=a[i-1]-a[i];}return greatestSumOfSubArray(diff);}/* *1.我的理解：从i=2开始遍历，找出i之前的最大元素,记为max,max减去当前元素a[i],如果这个差值比旧差值大，则更新旧差值 *2.引用原文： *我们定义diff[i]是以数组中第i个数字为减数的所有数对之差的最大值。 * 也就是说对于任意h（h < i），diff[i]≥number[h]-number[i]。diff[i]（0≤i<n）的最大值就是整个数组最大的数对之差。 * 假设我们已经求得了diff[i]，我们该怎么求得diff[i+1]呢？对于diff[i]，肯定存在一个h（h < i），满足number[h]减去number[i]之差是最大的，也就是number[h]应该是number[i]之前的所有数字的最大值。当我们求diff[i+1]的时候，我们需要找到第i+1个数字之前的最大值。 * 第i+1个数字之前的最大值有两种可能：这个最大值可能是第i个数字之前的最大值，也有可能这个最大值就是第i个数字。 * 第i+1个数字之前的最大值肯定是这两者的较大者。 * 我们只要拿第i+1个数字之前的最大值减去number[i+1]，就得到了diff[i+1]。 */public static int greatestLeftRightDiff02(int[] a){if(a==null||a.length<2){return Integer.MIN_VALUE;//min=1<<31}int len=a.length;int max=a[0];int diff=max-a[1];for(int i=2;i<len;i++){if(max<a[i-1]){max=a[i-1];}int newDiff=max-a[i];if(newDiff>diff){diff=newDiff;}}return diff;}public static int greatestSumOfSubArray(int[] array){int sum=0;int max=0;for(int i=0,len=array.length;i<len;i++){sum+=array[i];if(sum<=0){sum=0;}else{if(sum>max){max=sum;}}}return max;}}