数对之差的最大值 - xiewenfeng/test GitHub Wiki

在数组中，数字减去它右边的数字得到一个数对之差，求所有数对之差的最大值。 如在数组{2, 4, 1, 16, 7, 5, 11, 9}中，数对之差的最大值是11，是16-5的结果。

思路1：构造新数组，求新数组子序列的最大和

构造一个辅助数组diff[i] = array[i] - array[i+1],diff[i]+diff[i+1]+...+diff[j]=array[i]-array[j+1]; 这样就变成了求diff[i]+diff[i+1]+...+diff[j]的最大值，也就是连续子数组的最大和问题了，和前面的问题类似了。

private int maxSubTraction(int[] array) {
        if (array == null) return 0;
        if (array.length == 1) return array[0];
        if (array.length == 2) return array[0] - array[1];
        int length = array.length;
        int[] tempArray = new int[length-1];
        for (int i = 0; i < length-2; i ++) {
            tempArray[i] = array[i] - array[i+1];
        }
        return maxSumSubSequence(tempArray);

    }

    private int maxSumSubSequence(int[] array) {
        if (array == null) return 0;
        int maxSum = 0, temSum = 0;
        for (int data : array) {
            temSum += data;
            if (maxSum < temSum) {
                maxSum = temSum;
            } else if (temSum < 0) {
                temSum = 0;
            }
        }
        if (maxSum == 0) {
            maxSum = array[0];
            for (int i = 1; i < array.length; i ++) {
                if (array[i] > maxSum) {
                    maxSum = array[i];
                }
            }
        }
        return maxSum;

    }

思路2：根据前面一个数对差最大值求下一个数对差的最大值

假设已经找到数中中前i个数中数对之差的最大值为diff[i]=max{array[h]-array[k]}(0<=h<k<i),接下来就是新增一个数,求diff[i+1]怎么求，由于diff[i]值已求到，那么array[h]应该是数组中前i-1个数中最大的值，当新增一个数至i+1时，只需要找出数组中前i个数中的最大值，只需要将array[h]与array[i]进行比较，找到最大值，再把最大值减去array[i+1],将差值与diff[i]进行比较即可。

private int maxSubTraction2(int[] array) {
        if (array == null) return 0;
        if (array.length == 1) return array[0];
        if (array.length == 2) return array[0] - array[1];
        int length = array.length;
        int maxSubSum = array[0] - array[1];
        int max = array[0];
        for (int i = 2; i < length; i ++) {
            max = Math.max(max, array[i]);
            if (maxSubSum < (max - array[i])) {
                maxSubSum = max - array[i];
            }
        }
        return maxSubSum;

    }