题目来源：牛客网上面的牛课堂系列算法讲座 http://www.nowcoder.com/courses/6/2/3
给定一个长度为N(N>1)的整型数组A，可以将A划分成左右两个部分，左部分A[0..K]，右部分A[K+1..N-1]，K可以取值的范围是[0,N-2]。
求这么多划分方案中，左部分中的最大值减去右部分最大值的绝对值，最大是多少？
给定整数数组A和数组的大小n，请返回题目所求的答案。
测试样例：
[2,7,3,1,1],5
返回：6
1 class MaxGap { 2 public: 3 int findMaxGap(vector<int> A, int n) { 4 int m = -1; 5 for(int i = 0; i < n ;i++){ 6 if(m < A[i]) 7 m = A[i]; 8 } 9 return max((m-A[0]),(m-A[n-1])); 10 } 11 };
分析：假设全局最大值m在左边，那我们就希望右边的最大值越小越好。随着右边那个区间的左端点左移，右边的最大值不会变小，反倒是有可能变大，所以右边那个区间左端点越靠右越好。同理：最大值m划分到右边也类似，要求左边区间的右端点越靠左越好。所以，前n-1个元素的最大值m和A[0]或A[n-1]的差必然有一个是解。
代码和分析都是网友的贡献，这里仅作笔记。
