【左右最值最大值】c++

题目描述：

给定一个长度为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、遍历vector找到最大值，再根据最大值划分在哪个阵营进行讨论
2、若最大值等于A[0],此时要用A[0]-右边阵营的最大值，那么一定是A[0]-A[n-1];
思考：右边阵营一定包含A[n-1],若A[n-1]前有比它大的数，则差值就比减A[n-1]小了，若其前的数都小于它，那么一定是减它。故上面结论成立。
3、同理，若最大值等于A[n-1],则最大差值为A[n-1]-A[0]
4、若最大值在数列中间，那么，A[0]和A[n-1]谁小就减谁

代码：

//左右最值最大差
#include<iostream>
#include<vector>
using namespace std;
class MaxGap
{
public:
	int findMaxGap(vector<int> A, int n)
	{
		int maxnum = A[0];
		for (auto &i : A)
		{
			if (i > maxnum)
			{
				maxnum = i;
			}
		}
		if (maxnum == A[0])
		{
			return (A[0] - A[n - 1]);
		}
		else if (maxnum == A[n - 1])
		{
			return (A[n - 1] - A[0]);
		}
		return A[0] > A[n - 1] ? (maxnum - A[n - 1]) : (maxnum - A[0]);
	}
};

题目来源于牛客网