我的想法是：从左边第一个元素开始，向前比较，如果右边的数字比当前数字大，则向右移动（比如第一次会移动到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的值
文章参考何海涛大神文章
