首页 > 试题广场 >

左右最值最大差

[编程题]左右最值最大差
  • 热度指数：9256 时间限制：C/C++ 3秒，其他语言6秒 空间限制：C/C++ 32M，其他语言64M
  • 算法知识视频讲解

给定一个长度为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
算法知识视频讲解
添加回答
林家花美男头像 林家花美男
我来发一个我的好了。直接找max，min取两端的数。
不用考虑max在哪，因为无论在哪，min都只会<=max
class MaxGap {
public:
int findMaxGap(vector<int> A, int n) {
// write code here
int max=A[0],min;
for(int i=0;i<n;i++)
if(A[i]>max)
max=A[i];
min = A[0]>A[n-1]?A[n-1]:A[0];
return max-min;
}
};
编辑于 2017-03-27 14:49:00 回复(20)
RedstoneCMX头像 RedstoneCMX 
//首先找到最大值以及最大值所在的位置pos：
//1.如果pos=0，那么最大差值肯定是A[[0]-A[n-1]，因为左部分最大值必然是A[0]，
//右部分必然要包含A[n-1]，那么右部分最大值只会>=A[n-1]
//2.如果pos=n-1，那么最大差值肯定是A[n-1]-A[0]，道理和1一样
//3.如果pos是在中间位置，那么就是取(A[pos] - A[0]) 和(A[pos] - A[n-1])中最大的一个。 /***/
class MaxGap{
public:
    int findMaxGap(vector<int> A, int n) {
        // write code here
        int max = 0;
        int pos = 0;
        for(int i = 0; i < n; i++)
            if(max < A[i]){
            max = A[i];
            pos = i;
        }
        if(pos == 0)
            return A[0] - A[n-1];
        if(pos == n-1)
            return A[n-1] - A[0];
        int left = (A[pos] - A[0]);
        int right = (A[pos] - A[n-1]);
        return left > right ?  left: right;     
    }
};

编辑于 2016-04-19 20:31:52 回复(4)
Java
飞飞鱼20181211161418头像 飞飞鱼20181211161418

基于贪心算法的思想 这两个数中有一个肯定是数组的最大值。要使得差值最大，那么另一边的最大值应尽可
能的小。 假设最大值在左边，那么对于最大值右边的数组有很多种分法，每一种分法肯定都包含数组最后一
个数字即A[n-1]。 如果不取A[n-1]，取最后一个数字和最大值中间的任一数字A[i]。 若A[i]大于A[n-1]，那还
不如取最后一个数字；若最A[i] 小于A[n-1]， 那右半边的最大值肯定不是A[i]，所以无论如何右半边取最右
端数字。 假设最大值在右边，同理左半边取最左端数字。 只需用数组最大值减去数组两端较小的那个值即
可。
//老师讲的方法觉得受益良多，分享给大家

public class MaxGap {
    public int findMaxGap(int[] A, int n) {
        int max = 0;
        for(int i = 0;i<n;i++){
            if(max<A[i]){
                max = A[i];
            }
        }
        int ans1 = max - A[0];
        int ans2 = max - A[n - 1];
        if(ans1 > ans2){
            return ans1;
        }else{
            return ans2;
        }
    }
}
发表于 2019-08-10 18:52:50 回复(0)
HelloWorldn头像 HelloWorldn

我自己想出了一个解法，空间复杂度是３×ｎ，时间复杂度是Ｏ（３

×ｎ）。看了看别人写的题解，空间复杂度还可以有个小小的优化。

public int findMaxGap(int[] A, int n) {
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < A.length; i++) {
            if (max < A[i]) max = A[i];
        }
        return max - Math.min(A[0], A[n - 1]);
    }
发表于 2017-01-16 20:43:54 回复(1)
Java
南山北头像 南山北 
//简单说一下，不用开辟额外的空间，直接在本数组操作即可
//用三个指针就可以。一个指向K，其余两个以K为分界线，分别指向开头和K+1的位置
public int findMaxGap(int[] A, int n) {
        //leftmax存放左边数组的最大值，rightmax存放右边数组的最大值
        //value存放差值，temp存放每次的最大值
        int leftmax = 0 , rightmax = 0 ,value = 0 , temp = 0;
        //以K为分界线，K每次不断移动指针
        for(int K = 0 ; K < n-1 ; K++){
            //做一个判断。如果是第一次从左到K找最大数
            //就进入for循环，如果不是第一次找最大数，
            //因为前面已经在K-1个数中找到了最大数，所以不用从新开始找
            //只需要和第K个数比较一下就可以了
            if (value != 0 && A[K] > leftmax) {
                leftmax = A[K];
            } else {
                leftmax = A[0];
                // i每次从0开始遍历到K的位置，并且返回最大值
                for (int i = 0; i <= K; i++) {
                    leftmax = A[i] > leftmax ? A[i] : leftmax;
                }
            }
            rightmax = A[K+1];
            //j从K+1处开始遍历，并且返回数组最大值
            for(int j = K+1 ;j<n ; j++){
                rightmax = A[j]>rightmax?A[j]:rightmax;
            }
            //记录差值
            value = leftmax - rightmax;
            //差值小于0，取绝对值
            value = value<0?-value:value;
            //如果当前差值比上次差值大，替换差值
            temp = value>temp?value:temp;
        }
        //返回差值
        return temp;
    }

编辑于 2016-08-25 19:59:42 回复(1)
牛客302390号头像 牛客302390号 
class MaxGap {
public:
    int findMaxGap(vector<int> A, int n) {
        // write code here
        vector<int> mxL(n,0);//记录i位左侧最大值
        vector<int> mxR(n,0);//记录i位右侧最大值
        int ma=INT_MIN;
        for(int i=0;i<n;i++){//左侧
            if(i==0)mxL[i]=A[i];
            else
            mxL[i]=max(A[i],mxL[i-1]);
        }
        for(int i=n-1;i>=0;i--){//右侧
            if(i==n-1)mxR[i]=A[i];
            else mxR[i]=max(A[i],mxR[i+1]);
        }
        int res=INT_MIN;
        for(int i=0;i<n-1;i++){//求差
            res=max(res,abs(mxL[i]-mxR[i+1]));
        }
        return res;
    }
};

发表于 2016-03-23 21:59:13 回复(2)
LittleY头像 LittleY
int t=A[n-1];
        
int t1=A[0];
    Arrays.sort(A);
    int  x=A[n-1]-t;
        int y=A[n-1]-t1;
if(x>y){
      return x;
    }else{
        return y;
    }
思路：找到最大值  只需要与首尾比较 取最大的就行了，因为不管怎么划分 只能在首尾是较小值时才能取到最大值，如：{1,58,55,44,8,89,88,99,2}和{88,1,2,99,100}这样能看出来，不管怎么取都是对最大值与首尾进行计算。
发表于 2016-04-19 10:53:49 回复(0)
羽香头像 羽香
思路：先求最大值，最大值不在的分区一定从某一端开始，若分区中的数值比该段的端大，会减小该段最大值与最大值的差，所以只需比较最大值与两端的差别哪个大。 
#include <iostream>
#include <vector>
using namespace std;
class MaxGap {
public:
    int findMaxGap(vector<int> A, int n) {
        // write code here
        int max=A[0];
        for(int i=1;i<n;i++){
            if(A[i]>max)
                max=A[i];
        }
        return max-A[0]>max-A[n-1]?max-A[0]:max-A[n-1];
    }
};
/*
* 测试代码
*/
int main(){
	MaxGap a=MaxGap();
	int b[]={2,7,3,1,1};
	int lenB=sizeof(b)/sizeof(int);
	vector<int> c(b,b+lenB);
	cout<<a.findMaxGap(c,lenB)<<endl;
	
}

编辑于 2015-11-13 17:05:34 回复(0)
哗~啦~啦头像 哗~啦~啦 
//简单粗暴，容易理解，通俗易懂的代码：

import java.util.*;

public class MaxGap {
    public int findMaxGap(int[] A, int n) {
        int max1=A[0]; //定义一个最区间最大值初始为A[0]
        int max=Math.abs(A[0]-A[A.length-1]); 
        for(int i=0;i<A.length;i++){
            if(A[i]>max1){
                max1=A[i];
            }
            int max2=A[A.length-1]; //每次从n-1开始在右区间找最大值
            for(int j=A.length-1;j>i;j--){
                if(A[j]>max2){
                    max2=A[j];
                }
                if(Math.abs(max1-max2)>max){
                    max=Math.abs(max1-max2);
                }
            }
        }
        return max;
    }
}


发表于 2019-08-23 20:52:01 回复(1)
kestars头像 kestars 
import java.util.*;

public class MaxGap {
    public int findMaxGap(int[] A, int n) {
        // write code here
        int[][] dp=new int[n][n];
        for(int i=0;i<n;i++){
            dp[i][i]=A[i];
        }
        for(int i=0;i<n;i++){
            for(int j=i+1;j<n;j++){
                dp[i][j]=Math.max(dp[i][j-1],A[j]);
            }
        }
        int max=0;
        for(int k=0;k<n-1;k++){
            if(Math.abs(dp[0][k]-dp[k+1][n-1])>max){
                max=Math.abs(dp[0][k]-dp[k+1][n-1]);
            }
        }
        return max;
    }
}

发表于 2018-10-12 12:57:31 回复(0)
牛客LY头像 牛客LY 
#先遍历一遍A，存下来当前位置之前的最大值，
#再遍历一遍求出最大值即可，复杂度O（n）
# -*- coding:utf-8 -*-
class MaxGap:
    def findMaxGap(self, A, n):
        # write code here
        maxNum, max_ = [], A[0]
        for i in A:
            max_ = max(max_, i)
            maxNum.append(max_)
        res, max_r = float('-inf'), A[-1]
        for i in range(n - 2, -1, -1):
            max_r = max(max_r, A[i + 1])
            res = max(res, abs(maxNum[i] - max_r))
        return res

编辑于 2018-02-24 11:18:37 回复(0)
C/C++
nbgao头像 nbgao 
class MaxGap {
public:
    int findMaxGap(vector<int> A, int n) {
        int Max = A[0], Min;
        for(int i=0;i<n;i++)
        {
            if(A[i] > Max)
                Max = A[i];
            Min = A[0]>A[n-1]?A[n-1]:A[0];         }         return Max - Min;
    }
};

发表于 2017-10-13 01:13:32 回复(0)
柠檬叶子头像 柠檬叶子 
虽然题目不难，可是我还是弄了好久 注意的坑是左边的数组的个数依次增加到n-2 自然右边的个数就得减少 还有就是求左边的最大值与右边的最大的差的绝对值
 public static int findMaxGap(int[] A, int n)
        {
            // write code here
            int k = 0;
            int max = 0, sub = 0;       
            for (k = 0; k <= n - 2; k++)
            {
               int q = 0,r = 0;
                int[] left = new int[k+1];
                int[] right = new int[n-k-1];
                for (int i = 0; i < A.Length; i++)
                {
                    if (i > k)
                    {
                        right[r] = A[i];
                        r++;
                    }
                    else
                    {
                        left[q] = A[i];
                        q++;
                    }
                }
                sub = left.Max() - right.Max();
                if(sub<0)
                {
                    sub *= -1;
                }
                if(sub>max)
                {
                    max = sub;
                }
                 }
            return max;           
        }
发表于 2017-03-13 21:10:11 回复(0)
June1993头像 June1993
public class MaxGap {
    public int findMaxGap(int[] A, int n) {
        int res=0,max=A[0],tmp=0;
  for(int i=1;i<n;i++)
  {
      if(A[i]>max)
      {
          max=A[i];
          tmp=i;
      }
  }
     if(tmp==0)
         res=A[0]-A[n-1];
     else{
         if(tmp==n-1)
             res=A[n-1]-A[0];
         else
         {
            res=A[0]<A[n-1]?A[tmp]-A[0]:A[tmp]-A[n-1];
         }
     }
        return res;
    }
}

发表于 2016-11-04 21:44:59 回复(0)
Java
曙光女神头像 曙光女神 
最原始的办法，分别找到左边与右边的最大值，相减取绝对值。
不过本题的说法不严谨。。。有点歧义 
public int findMaxGap(int[] A, int n)
	{
        int maxDisOfTwoGroup = Integer.MIN_VALUE;
        for(int k = 0; k <(n-1);k++)
        {
        	int maxNumberOfLeft = A[0];
            for(int i = 0; i <= k ; i++)
            {
            	if(A[i] > maxNumberOfLeft)
            		maxNumberOfLeft = A[i];
            }
            
            int maxNumberOfRight = A[k+1];
            for(int i = (k+1); i < n ;i++)
            {
            	if(A[i] > maxNumberOfRight)
            		maxNumberOfRight = A[i];
            }
            
            if((maxNumberOfLeft-maxNumberOfRight) 
            		> maxDisOfTwoGroup)
            {
            	maxDisOfTwoGroup = 
            			Math.abs(maxNumberOfLeft-maxNumberOfRight);
            }
        }
        
        System.out.println(maxDisOfTwoGroup);
        return maxDisOfTwoGroup;
    }

发表于 2016-09-04 19:34:03 回复(0)
牛客703246号头像 牛客703246号 
#没想到好的办法，依次循环
# -*- coding:utf-8 -*-
class MaxGap:
    def findMaxGap(self, A, n):
        # write code here
        max_A=0
        for k in range(1,n):
            if abs(max(A[:k])-max(A[k:]))>=max_A:
                max_A=abs(max(A[:k])-max(A[k:]))
        return max_A

发表于 2016-05-14 12:52:06 回复(1)
尼见头像 尼见 
先把寻找数组最大值单独提出来一个方法，这样看着还简单，然后把原数组A分成两个数组，分别调用方法，比较最大值即可，时间复杂度为o(n^2)，不知道还有没有更简单的方法 public class MaxGap {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int A[] = { 2, 7, 3, 1, 1 };
		new MaxGap().findMaxGap(A, 5);
	}

	public int findMaxGap(int[] A, int n) {
		// write code here
		int max = 0;
		for (int k = 0; k <= n - 2; k++) {
			int before[] = new int[k + 1], after[] = new int[n - k - 1];
			for (int i = 0, j = k + 1; (i <= k) || (j <= n - 1); i++, j++) {
				if (i <= k) {
					before[i] = A[i];
				}
				if (j <= n - 1) {
					after[j - k - 1] = A[j];
				}
			}
			int maxParam = Math.abs(findMax(before) - findMax(after));
			max = Math.max(maxParam, max);
		}
		System.out.println(max);
		return max;
	}

	public int findMax(int A[]) {
		int max = 0;
		if (A.length == 1) {
			return A[0];
		}
		for (int i = 0; i < A.length - 1; i++) {
			if (A[i] - A[i + 1] > 0) {
				max = A[i];
				A[i + 1] = A[i];
			} else {
				max = A[i + 1];
			}
		}
		return max;
	}

}


发表于 2016-04-29 20:31:08 回复(0)
xiaoxu头像 xiaoxu 
class MaxGap {
public:
    int findMaxGap(vector<int> A, int n) {
        // write code here
        int s=0,max_left=0,max_right=0;
        int i,k,j;
        for(k=0;k<=n-2;k++)
            {
            max_left=A[0];
            max_right=A[k+1];
            for(i=0;i<=k;i++)//求左边数组的最大值
                {
                if(A[i]>max_left)
                    max_left=A[i];
                
                   }
            for(j=k+1;j<n;j++)//求右边数组的最大值
                {
                if(A[j]>max_right)
                    max_right=A[j];
                }
            if(s<abs(max_right-max_left))
                s=abs(max_left-max_right);
        }
        return s;//输出最大绝对值
    }
};

发表于 2016-03-11 19:46:37 回复(1)
onehuang头像 onehuang
我对这题目的思路：1，求出数组中的最大值，然后从最大值的下标开始求出后面所有的数的最小值，然后求绝对值。2，求出数组中的最小值，然后求出从0到最小值所在的下标之间的最大值，求绝对值。最后对两次求出的值比较，选择最大的作为结果！
发表于 2015-09-11 08:46:38 回复(2)
积累面试头像 积累面试
直接最大值减最小值不就可以了？
发表于 2015-09-11 10:42:18 回复(3)
提交观点

问题信息

贪心
来自：面试常考算法题(二)
难度：
95条回答 23470浏览

热门推荐

通过挑战的用户

查看代码

相关试题

左右最值最大差

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号