最大的LeftMax与rightMax之差绝对值
浏览数：17 /
时间：2015年06月09日
这两天去 牛客网 混了下，遇到的几道题都很有意思，尤其是今晚这道，比赛时不会做，后来看了别人的代码才突然想通的，题目链接：
想了一晚都没想出，后来看了别人精简的代码后才想通，然后自己用C++写了下也过了：
至于算法思路，为了给一个群友说清楚码了一大堆字，好累，后来想截图时却发现聊天记录没有了气泡模式，还是适当复制粘贴一下吧：
首先选出的左右两部分的那两个最大的数，其中一个肯定是整个数组中最大的数，它可能被分在左边或右边，假设它在左边的话，那么只需要使右边那部分的最大的数最小就行，这样就能得出答案。而右边那部分一定包含数组最右边那个数（k的边界条件），假设刚才已找出的整个数组中最大的数下标为k，最右边那个数的下标为len-1，假设在len-1前到k这段区间中的数都比vec[len-1]小，那么答案就是vec[k]-vec[len-1]，若果这段区间内有比vec[len-1]大的，那么就把它归入左边部分，这样子左边部分最大值还是vec[k]，而右边部分最大值还是vec[len-1]，所以这样子最终答案就是vec[k]-vec[len-1]。同理，当vec[k]在右边部分时可以得出答案为vec[k]-vec[0]，所以最终答案就是 max( Max-vec[0], Max-vec[len-1] ) 了。
郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。
