当前位置:网站首页>左右最值最大差问题
左右最值最大差问题
2022-07-04 18:48:00 【GreyZeng】
左右最值最大差问题
作者:Grey
原文地址: 左右最值最大差问题
题目链接
描述
给定一个长度为N(N>1)的整型数组A,可以将A划分成左右两个部分,左部分
A[0..K]
,右部分A[K+1..N-1]
,K可以取值的范围是[0,N-2]
。求这么多划分方案中,左部分中的最大值减去右部分最大值的绝对值,最大是多少?
给定整数数组A和数组的大小n,请返回题目所求的答案。
测试样例:
A:[2,7,3,1,1]
n:5
返回:6
主要思路
假设数组长度为len
,遍历一遍数组,得到数组的最大值max
,然后比较0
位置和len-1
位置的值,取较小的那个,假设为m
,则max - m
即为答案。
完整代码
public class MaxGap {
public int findMaxGap(int[] A, int n) {
int max = A[0];
int len = A.length;
for (int i = 1; i < len; i++) {
max = Math.max(A[i], max);
}
return max - (Math.min(A[0], A[len - 1]));
}
}
证明
由于全局最大值是max
,所以无论max
被划分到哪个部分,都会成为这部分的最大值。假设max
被划分到了右边部分,所以右边部分的最大值就是max
,假设左边部分的最大值是m
,那么max - m
即为一个答案候选。要使得max - m
最大,而左边部分不能为空,所以左边部分必须要包含0
位置的值,所以,在左边只包含0
位置值的时候,max - m
才能做到最大,即:max - arr[0]
;同理,假设max
被划分到了左边,右边最大值假设为n
,要使得max - n
最大,len - 1
位置的值又必须包含在右边,那么max - arr[len-1]
才是最大的。所以最终的答案就是:
max - Math.min(arr[0],arr[len-1]);
更多
边栏推荐
- Niuke Xiaobai month race 7 who is the divine Archer
- What are the consequences of closing the read / write channel?
- 1011 World Cup betting (20 points) (pat a)
- 【深度学习】一文看尽Pytorch之十九种损失函数
- C语言-入门-基础-语法-流程控制(七)
- What should we pay attention to when doing social media marketing? Here is the success secret of shopline sellers!
- 记一次 .NET 某工控数据采集平台 线程数 爆高分析
- Crystal optoelectronics: ar-hud products of Chang'an dark blue sl03 are supplied by the company
- Lingyun going to sea | 10 jump &huawei cloud: jointly help Africa's inclusive financial services
- 凌云出海记 | 文华在线&华为云:打造非洲智慧教学新方案
猜你喜欢
Employment prospects and current situation of Internet of things application technology
What is the application technology of neural network and Internet of things
Key rendering paths for performance optimization
[ismb2022 tutorial] the picture shows the precision medicine of learning. Marinka zitnik, Harvard University, keynote speaker, with 87 ppt
Actual combat simulation │ JWT login authentication
Dark horse programmer - software testing - stage 08 2-linux and database-23-30-process port related, modify file permissions, obtain port number information, program and process related operations, Li
记一次 .NET 某工控数据采集平台 线程数 爆高分析
【ISMB2022教程】图表示学习的精准医疗,哈佛大学Marinka Zitnik主讲,附87页ppt
How is the entered query SQL statement executed?
精选综述 | 用于白内障分级/分类的机器学习技术
随机推荐
[ismb2022 tutorial] the picture shows the precision medicine of learning. Marinka zitnik, Harvard University, keynote speaker, with 87 ppt
如何让你的小游戏适配不同尺寸的手机屏幕
2022 version of stronger jsonpath compatibility and performance test (snack3, fastjson2, jayway.jsonpath)
Selected review | machine learning technology for Cataract Classification / classification
长城证券开户安全吗 股票开户流程网上开户
Abc229 summary (connected component count of the longest continuous character graph in the interval)
How to adapt your games to different sizes of mobile screen
Swagger suddenly went crazy
[QNX hypervisor 2.2 user manual]6.3.1 factory page and control page
Delete the characters with the least number of occurrences in the string [JS, map sorting, regular]
Oracle database, numbers Force 2 decimal places to display-Alibaba Cloud
实战模拟│JWT 登录认证
应用实践 | 蜀海供应链基于 Apache Doris 的数据中台建设
记一次 .NET 某工控数据采集平台 线程数 爆高分析
Pointnet / pointnet++ point cloud data set processing and training
ICML 2022 | meta proposes a robust multi-objective Bayesian optimization method to effectively deal with input noise
Is it necessary to apply for code signing certificate for software client digital signature?
Integretee integrates into Moonriver through xcm, bringing enterprise class privacy solutions to its ecosystem
1005 spell it right (20 points) (pat a)
C # better operation mongodb database