数对差

我的想法是：从左边第一个元素开始，向前比较，如果右边的数字比当前数字大，则向右移动（比如第一次会移动到4），然后同样的，从最右边开始，向左边比较，如果左边的比当前小，则向左移动（比如现在11>9，则不移动）
然后我们相减，得到一个值，保存下来。然后我们左边的数字leftMax向右移动，直到遇到一个比当前大的，然后更新这个值（此时我们更新为16），然后我们把这个值减去右边的，更新当前的差值
如果我们向右边寻找一直都没有找到比当前更大的值，则。。

等等，我这个思路有bug啊，比如上面的数组里面，5的右边有一个17，那这样得到的值是17-9啊！

寻找最大值没有意义啊！擦。。

---

然后我看了例程。。发现水还是蛮深的

先介绍一个简单的，思路1：

1,求相邻元素差

我们把源数组相邻两个元素相减，得到另一个长为n-1的数组，然后就转为另一个已经解决过的问题了：求数组中和最大的连续子数组

这个子问题的思路简单介绍一下：
从第一个开始往前加，currentsum为负值则丢弃，然后不断更新MaxSum，遍历一遍即可

//diff 为相邻数相减得到的数组
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;
}

2，分治

其实分治吧，就是递归
这里是把一个数组分为两个部分，然后分别求左边的最大差leftDiff，右边的最大差rightDiff，以及跨两部分的crossDiff

int MaxDiffCore(int* start, int* end, int* max, int* min)
{
    if (end == start)
    {
        *max = *min = *start;
        return 0x80000000;
    }
    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;
}

3，动态规划

最后一种思路。。好吧我发现我最开始的想法是可以的，稍微修改一下

我的想法是：从左边第一个元素开始，向前比较，如果右边的数字比当前数字大，则向右移动（比如第一次会移动到4），然后同样的，从最右边开始，向左边比较，如果左边的比当前小，则向左移动（比如现在11>9，则不移动）
然后我们相减，得到一个值，保存下来。然后我们左边的数字leftMax向右移动，直到遇到一个比当前大的，然后更新这个值（此时我们更新为16），然后我们把这个值减去右边的，更新当前的差值
如果我们向右边寻找一直都没有找到比当前更大的值，则。。

我们从左向右，保存一个currentMax，然后保存一个MaxDiff，这两个结果在遍历的过程中不断更新就好了，
当然要注意的一点就是，我们每次只关心当前的一个元素，也就是只对当前元素arr[i]更新currentSum,MaxDiff
这样思维更简单更清晰有没有啊！

int maxDiff_3(int* arr, int len)
{
    if (!arr || len < 2)
        return 0;
    int currMax = 0;
    int MaxDiff=0;
    int currDiff = 0;
    for (int i = 1; i < len; i++)
    {
        if (arr[i - 1] > currMax)
            currMax = arr[i - 1];
        currDiff = currMax - arr[i];
        if (currDiff > MaxDiff)
            MaxDiff = currDiff;
    }
    return MaxDiff;
}

我想了一下，我之所以在尝试的时候出现问题是因为，我觉得currentMax的值一定影响到maxDiff的值，这是不成立的。
因为我们要先有一个判断才会改变maxDiff的值

文章参考何海涛大神文章