程序员面试题精选100题（61）-数对之差的最大值[算法]

 

    int* middle = start + (end - start) / 2;

 

    int maxLeft, minLeft;

    int leftDiff = MaxDiffCore(start, middle, &maxLeft, &minLeft);

 

    int maxRight, minRight;

    int rightDiff = MaxDiffCore(middle + 1, end, &maxRight, &minRight);

 

    int crossDiff = maxLeft - minRight;

 

    *max = (maxLeft > maxRight) ? maxLeft : maxRight;

    *min = (minLeft < minRight) ? minLeft : minRight;

 

    int maxDiff = (leftDiff > rightDiff) ? leftDiff : rightDiff;

    maxDiff = (maxDiff > crossDiff) ? maxDiff : crossDiff;

    return maxDiff;

}

在函数MaxDiffCore中，我们先得到第一个子数组中的最大的数对之差leftDiff，再得到第二个子数组中的最大数对之差rightDiff。接下来用第一个子数组的最大值减去第二个子数组的最小值得到crossDiff。这三者的最大值就是整个数组的最大数对之差。

解法二：转化成求解子数组的最大和问题

接下来再介绍一种比较巧妙的解法。如果输入一个长度为n的数组numbers，我们先构建一个长度为n-1的辅助数组diff，并且diff[i]等于numbers[i]-numbers[i+1]（0<=i<n-1）。如果我们从数组diff中的第i个数字一直累加到第j个数字（j > i），也就是