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

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中最大的连续子数组之和。我们在本系列的博客的第3篇《求子数组的最大和》中已经详细讨论过这个问题的解决方法。基于这个思路，我们可以写出如下代码：

int MaxDiff_Solution2(int numbers[], unsigned length)

{

    if(numbers == NULL || length < 2)

        return 0;

 

    int* diff = new int[length - 1];

    for(int i = 1; i < length; ++i)

        diff[i - 1] = numbers[i - 1] - numbers[i];

 

    int currentSum = 0;

    int greatestSum = 0x80000000;

    for(int i = 0; i < length - 1; ++i)

    {

        if(currentSum <= 0)

            currentSum = diff[i];

        else

            currentSum += diff[i];

 

        if(currentSum > greatestSum)

            greatestSum = currentSum;

    }

 

    delete[] diff;

 

    return greatestSum;

} 

解法三：动态规划法

既然我们可以把求最大的数对之差转换成求子数组的最大和，而子数组的最大和可以通过动态规划求解，那我们是不是可以通过动态规划直接求解呢？下面我们试着用动态规划法直接求数对之差的最大值。