首页 > 试题广场 >

最大的LeftMax与rightMax之差绝对值

[编程题]最大的LeftMax与rightMax之差绝对值
  • 热度指数：1014 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
  • 算法知识视频讲解
给定一个长度为N的整型数组arr，可以划分成左右两个部分： 左部分arr[0..K]，右部分arr[K+1..arr.length-1]，K可以取值的范围是[0,arr.length-2] 求这么多划分方案中，左部分中的最大值减去右部分最大值的绝对值，最大是多少？ 例如： [2,7,3,1,1] 当左部分为[2,7]，右部分为[3,1,1]时，左部分中的最大值减去右部分最大值的绝对值为4; 当左部分为[2,7,3]，右部分为[1,1]时，左部分中的最大值减去右部分最大值的绝对值为6; 最后返回的结果为6。 注意：如果数组的长度为N，请尽量做到时间复杂度O(N)，额外空间复杂度O(1)
算法知识视频讲解
添加回答
推荐
Ian头像 Ian
整个数组最大值要么在左，要么在右。
若在左，要得到结果，则要求分开后右边数组的最大值尽量小，显然max(a,b,c) >= a (or b, c),因而右边数组只包含最右元素时右边的最大值最小。
若在右，类似。
对两种情况加个判断，得到最优解。 

class Solution {
public:
 /**
 *  求左部分中的最大值减去右部分最大值的绝对值
 *  vec: 输入数组
 *  len vec的长度
 *  返回：左部分中的最大值减去右部分最大值的绝对值    */

 int getMaxABSLeftAndRight(vector<int> vec, int len) {
 if (len == 0) {
 return 0;
 }         
 int max = vec[0];    
 for (int i = 1; i < len; i++) {
 if (vec[i] > max) {
 max = vec[i];
 }
 }         
 return max - (vec[0] < vec[len - 1] ? vec[0] : vec[len - 1]);
 }
};
编辑于 2015-03-25 20:48:25 回复(9)
你为什么不开大头像 你为什么不开大 
public class Solution {
	/**
	 *	求左部分中的最大值减去右部分最大值的绝对值
	 *	arr：输入数组
	 *	返回：左部分中的最大值减去右部分最大值的绝对值
	 */
    public int getMaxABSLeftAndRight(int[] arr) {
        int max = arr[0];
        //找到整个数组的最大值
        for(int t : arr){
            if(t > max)
                max = t;
        }
        /*
        数组中所有数字都小于等于max，也就是k左边数字都小于max
        设最右数字为r;
        假设[k+1,arr.length-1]中存在比r大 比max小的数字，很明显结果不合题意，k要++
        假设[k+1,arr.length-1]中不存在比r大的数字，那么r就是最大的
         */

        return Math.max(Math.abs(max-(arr[arr.length-1])),Math.abs(max-(arr[0])));
    }
}

编辑于 2016-09-23 10:47:36 回复(1)
月落头像 月落 
public class test {
 public static void main(String[] args) {
 
 int[] arr = {1,3,7,2,4,5,3,9,1,3};
 int max = arr[0];
 int x = 0;
 for (int i = 0; i < arr.length; i ++){
 if (max < arr[i]){
 max = arr[i];
 x = i;
 }
 }
 int max_c = max - arr[0];
 for ( int i = 0; i < x; i ++ ){
 if (max_c > max - arr[i])
 max_c = max - arr[i];
 }
 int max_d = max - arr[arr.length-1];
 for (int i = arr.length - 1; i > x; i --){
 if(max_d >max - arr[i])
 max_d = max - arr[i];
 }
 System.out.println(max_d>max_c?max_d:max_c);
 }
}

编辑于 2015-03-25 10:59:42 回复(0)
writezen头像 writezen 
static int getMaxABSLeftAndRight(int[] arr) {
     int[] arrTemp=new int[arr.length-1];
     for(int k=0;k<arr.length-1;k++){
     arrTemp[k]=Math.abs(getMax(arr,0,k)- getMax(arr,k+1,arr.length-1));
     }
     return getMax(arrTemp,0,arrTemp.length-1);
 }
 static int getMax(int[] arr,int startPosition,int endPosition){
     int max=0;
     for(int i=startPosition;i<=endPosition;i++){
         if(arr[i]>max){
         max=arr[i];
         }
     }
     return max;
 }

编辑于 2015-03-13 08:34:01 回复(0)
牛客424358729号头像 牛客424358729号

输入：数组/数组长度/k

1. 判断k的有效性

2. 第一段arr1….(k-1)最大值，

3. 第二段最大值

4. 绝对值

编辑于 2021-11-24 20:29:36 回复(0)
松华皮蛋me头像 松华皮蛋me 
public class Solution {
	/**
	 *	求左部分中的最大值减去右部分最大值的绝对值
	 *	arr：输入数组
	 *	返回：左部分中的最大值减去右部分最大值的绝对值
	 */
	public int getMaxABSLeftAndRight(int[] arr) {
		int[] lArr = new int[arr.length];
        int[] rArr = new int[arr.length];
        lArr[0]=arr[0];
        rArr[arr.length-1] = rArr[arr.length-1];
        for(int i=1;i<arr.length;i++) {
            lArr[i] = Math.max(lArr[i-1],arr[i]);
        }
        for(int i=arr.length-2;i>=0;i--) {
            rArr[i] = Math.max(rArr[i+1],arr[i]);
        }
        int max = 0;
        for(int i=0;i<arr.length-1;i++) {
            max = Math.max(max,Math.abs(lArr[i]-rArr[i+1]));
        }
        return max;
	}
}

发表于 2016-08-17 22:59:49 回复(0)
Shield_W头像 Shield_W 
public class Solution {
	public int getMaxABSLeftAndRight(int[] arr) {
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < arr.length; i++) {
            max = Math.max(max, arr[i]);
        }
        return max - Math.min(arr[0], arr[arr.length - 1]);
	}
}

发表于 2016-08-14 19:22:10 回复(0)
等待2017头像 等待2017 
class Solution {
public:
	/**
	 *	求左部分中的最大值减去右部分最大值的绝对值
	 *	vec: 输入数组
     *  len vec的长度
	 *	返回：左部分中的最大值减去右部分最大值的绝对值
	 */
	int getMaxABSLeftAndRight(vector<int> vec, int len) {
        vector<int>::iterator p,pos1,pos2;
        p=vec.begin();
        int k;
        int m=0;
        for(k=0;k<len-1;k++){
            pos1=max_element(p,p+k+1);
            pos2=max_element(p+k+1,p+len);
            m=max(m,(*pos1>*pos2?(*pos1-*pos2):(*pos2-*pos1)));
            
        }
        return m;

    }
};

发表于 2015-10-24 12:07:47 回复(0)
晏金龙头像 晏金龙

static int getMaxABSLeftAndRight(int[] arr) {
     int[] arrMax=new int[arr.length-1];
     for(int k=0;k<arr.length-1;k++){
     arrMax[k]=Math.abs();
     }
     return getMax(arrMax,0,arrMax.length-1);
 }
 static int getMax(int[] arr,int start,int end){
     intmax=0;
     for(inti=start;i<=end;i++){
         if(arr[i]>max){
         max=arr[i];
         }
     }
     return max;
 }
发表于 2015-09-02 18:04:14 回复(0)
牛客165815号头像 牛客165815号 
public class Solution {
 
     public static int getMaxABSLeftAndRight(int[] arr) {
          int res = Integer.MIN_VALUE;
          for (int i = 0; i != arr.length - 1; i++) {
              int maxLeft = Integer.MIN_VALUE;
              for (int j = 0; j != i + 1; j++) {
                  maxLeft = Math.max(arr[j], maxLeft);
              }
             int maxRight = Integer.MIN_VALUE;
             for (int j = i + 1; j != arr.length; j++) {
                 maxRight = Math.max(arr[j], maxRight);
             }
             res = Math.max(Math.abs(maxLeft - maxRight), res);
         }
         return res;
     }

     public static int getMaxABSLeftAndRightBetter(int[] arr) {
         int[] leftMaxArr = new int[arr.length];
         leftMaxArr[0] = arr[0];
         int[] rightMaxArr = new int[arr.length];
         rightMaxArr[arr.length - 1] = arr[arr.length - 1];
         for (int i = 1; i != arr.length; i++) {
            leftMaxArr[i] = Math.max(leftMaxArr[i - 1], arr[i]);
         }
         for (int i = arr.length - 2; i != -1; i--) {
             rightMaxArr[i] = Math.max(rightMaxArr[i + 1], arr[i]);
         }
         int max = 0;
         for (int i = 0; i != arr.length - 1; i++) {
             max = Math.max(max, Math.abs(leftMaxArr[i] - rightMaxArr[i + 1]));
         }
         return max;
     }
 
     public static int getMaxABSLeftAndRightBest(int[] arr) {
         int max = Integer.MIN_VALUE;
         for (int i = 0; i != arr.length; i++) {
             max = Math.max(arr[i], max);
         }
         return max - Math.min(arr[0], arr[arr.length - 1]);
     }
 
 }
发表于 2015-05-27 00:13:06 回复(0)
AndyJee头像 AndyJee
class Solution {
public:
/**
* 求左部分中的最大值减去右部分最大值的绝对值
* vec: 输入数组
     *  len vec的长度
* 返回：左部分中的最大值减去右部分最大值的绝对值
*/
int getMaxABSLeftAndRight(vector<int> vec, int len) {
        if(len<=0)
            return 0;
        int max=vec[0];
        for(int i=1;i<len;i++){
            if(vec[i]>max)
                max=vec[i];
        }
        if(vec[0]<=vec[len-1])
            return max-vec[0];
        else
            return max-vec[len-1];
        
    }
};
发表于 2015-04-12 08:22:11 回复(0)
叫一个响亮的名字头像 叫一个响亮的名字
只有三个值是有意义的，最大值，最左边的点，最右边的点。左边数组中的最大值肯定是大于等于最左边的点，同理右边数组。找到最大值的，将最大值归在左右点中大的那部分 
public class Solution {
    publicintgetMaxABSLeftAndRight(int[] arr) {
        intmaxNum=arr[0];
        intlen=arr.length;
        for(inti=1;imaxNum){
                maxNum=arr[i];
            }    
        }
        if(arr[0]>arr[len-1]) return maxNum-arr[len-1];
        else return maxNum-arr[0];
 
    }
}
发表于 2015-04-08 09:57:45 回复(0)
——天蝎座头像 ——天蝎座
public static void main(String args[]){
  String str = "1asdasd12qweqerwer";
  for(int i=str.length()-1;i>=0;i--){
   System.out.print(str.substring(i, i+1));
  }
    }
发表于 2015-03-31 20:47:51 回复(0)
卡伊露头像 卡伊露
import java.util.Arrays;
public class Solution {
 public int getMaxABSLeftAndRight(int[] arr) {
  int[] result = new int[arr.length - 1];
  for (int k = 1; k <= arr.length - 1; k++) {
   int[] arrSub1 = Arrays.copyOf(arr, k);
   int[] arrSub2 = Arrays.copyOfRange(arr, k, arr.length);
   Arrays.sort(arrSub1);
   Arrays.sort(arrSub2);
   result[k-1] = Math.abs(arrSub1[arrSub1.length - 1]
     - arrSub2[arrSub2.length - 1]);
  }
  Arrays.sort(result);
  return (result[result.length - 1]);
 }
}
发表于 2015-03-31 12:44:18 回复(0)
约克超头像 约克超
只有三个值是有意义的，最大值和左右两个端点值。结果就是最大值与左右端点差值绝对值的较大值。 

public class Solution {
 /**
 *	求左部分中的最大值减去右部分最大值的绝对值
 *	arr：输入数组
 *	返回：左部分中的最大值减去右部分最大值的绝对值
 */
    public int getMaxABSLeftAndRight(int[] arr) {
        int max = getMax(arr);
        return abs(max
                - (arr[0] < arr[arr.length - 1] ? arr[0] : arr[arr.length - 1]));
    }

    private int getMax(int[] arr) {
        int max = arr[0];
        for (int i = 1; i < arr.length; i++) {
            if (max < arr[i])
                max = arr[i];
        }
        return max;
    }

    private int abs(int a) {
        return a > 0 ? a : -a;
    }
}

编辑于 2015-03-28 17:48:32 回复(0)
dqstrong头像 dqstrong
#include<iostream>
using namespace std;
#define MAXSIZE 10
int main(){
int arr[MAXSIZE]={
1,3,7,2,4,5,3,9,1,3
};
int LMax=arr[0],RMax=arr[MAXSIZE-1],Max=LMax-RMax;
for(int i=1;i<MAXSIZE-1;i++){
if(LMax<arr[i]){
if(Max>0){
Max+=(arr[i]-LMax);
}
LMax=arr[i];
}
if(RMax<arr[i+1]){
if(Max<0)
Max-=(arr[i+1]-RMax);
RMax=arr[i+1];
}
if(abs(LMax-RMax)>abs(Max))
Max=LMax-RMax;
}
cout<<"Max is:"<<abs(Max)<<endl;
return 0;
}
发表于 2015-03-26 21:58:22 回复(0)
牛客966400号头像 牛客966400号
发表于 2015-03-24 21:45:16 回复(0)
↑↓＆√×￥头像 ↑↓＆√×￥
对数组排序，然后用最大值减掉最小值应该就是就是最大的差值了吧！不会java和c，写不出代码
发表于 2015-03-24 10:07:10 回复(0)
wikizhu头像 wikizhu
先确定最大值位置j，在[0,j)中从0开始找最大值最小的字数组，令最大值为leftMax;在（j,n-2]中从n-2开始反向找最大值最小的数组，令最大值为rightMax;比较leftMax和rightMax，去较小者与data[j]做差，取绝对值即为所求。 
class Solution {
public:
 /**
 *	求左部分中的最大值减去右部分最大值的绝对值
 *	vec: 输入数组
     *  len vec的长度
 *	返回：左部分中的最大值减去右部分最大值的绝对值
 */
 int getMaxABSLeftAndRight(vector<int> data, int n) {
        int i,j=0;
        for(i=1;i<n;i++){//让j指向最大元素 
            if(data[i]>data[j]){
                j=i;
            }
        }

        int leftMax=data[0],rightMax=data[n-1];//尽量让这两个尽可能小
        for(i=1;i<j;i++){
            if(data[i]>=leftMax)
                break;
        } 
        for(i=n-2;i>j;i--){
            if(data[i]>=rightMax)
                break;
        }

        if(leftMax<rightMax)
              return abs(data[j]-leftMax);
        else
              return abs(data[j]-rightMax);

 }
};

编辑于 2015-03-20 20:02:35 回复(0)
提交观点

问题信息

贪心 数组
来自：BAT 2015实习内...
难度：
19条回答 12838浏览

热门推荐

通过挑战的用户

相关试题

最大的LeftMax与rightMax之差绝对值

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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