【分类讨论】【解析几何】【 数学】【推荐】1330. 翻转子数组得到最大的数组值

本文主要是介绍【分类讨论】【解析几何】【 数学】【推荐】1330. 翻转子数组得到最大的数组值,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

作者推荐

视频算法专题

本文涉及知识点

分类讨论 解析几何

LeetCode1330. 翻转子数组得到最大的数组值

给你一个整数数组 nums 。「数组值」定义为所有满足 0 <= i < nums.length-1 的 |nums[i]-nums[i+1]| 的和。
你可以选择给定数组的任意子数组,并将该子数组翻转。但你只能执行这个操作 一次 。
请你找到可行的最大 数组值 。
示例 1:
输入:nums = [2,3,1,5,4]
输出:10
解释:通过翻转子数组 [3,1,5] ,数组变成 [2,5,1,3,4] ,数组值为 10 。
示例 2:
输入:nums = [2,4,9,24,2,1,10]
输出:68
提示:
1 <= nums.length <= 3*104
-105 <= nums[i] <= 105

分类讨论

n = nums.length
一,不翻转。
二,翻转nums[0,i2)。i2 ∈ \in [0,n)。没必要翻转两个数组。
三,翻转nums[i1,n)。i1 ∈ \in [0,n)。
四,翻转nums[i1,i2),i1不为0,i2不为n,i1和i2是合法下标,i1<i2。nums[i1-1]和nums[i2]都会发生变化。
翻转之前:|a-b|+|c-d| 翻转之后:|a-c|+|b-d|。
翻转后的数组值变大 ⟺ \iff f(a,b,c,d) = |a-c|+|b-d| -|a-b|+|c-d| > 0。
令这4个数,下标从小大到大为a(nums[i1-1]),b(nums[i1]),c,d。
两点简化:
简化一,只需要考虑a <= c。
简化二,只需要考虑a <= b。

简化一证明

某组数a1,b1,c1,d1 ,a1 < c1 。
某外一组数{c1,d1,a1,b1} = f(c1,d1,a1,b1)=|c1-a1|+|d1-b1| - |c1-d1|-[a1-b1|
第一项第二项取反:|a1-c1|+|b1-d1|
第三项第四项互换:-|a1-b1|-|c1-d1|。
故:f(c1,d1,a1,b1) = f(a1,b1,c1,d1)

简化二证明:

某组数a1,b1,c1,d1 a1 > b1。
另外一组数{b1,a1,d1,c1} , f(b1,a1,d1,c1)=|b1-d1|+[a1-c1| -|b1-a1|-|d1-c1|
交换第一项和第二项目:|a1-c1|+|b1-d1|
第三项、第四项目,取反:-|a1-b1| - |c1,d1|
故:f(b1,a1,d1,c1) = f(a1,b1,c1,d1)。

等效问题

有一维四点a,b,c,d。 a <=b,a<=c。
线段ac的长度+线段bd的长度,能否大于线段ab的长度+线段cd的长度。
一,假定 b < c。
在这里插入图片描述
第一二种情况,两者有重合部分,长度不变。
第三四中情况,两者无重合部分,长度增加 两条线段的间隙 × \times × 2
二,b > c。
在这里插入图片描述
全部变短或不变,全部部分重合或全部重合。

结论

a<b a<c ,两条线段有重叠部分,则变短或不变。 没有重叠部分,变长间隙长度 × \times × 2。
上文已经证明了 两种简化的结果一样,现在来证明两个简化的判断条件一致。

简化一证明

某组数a1,b1,c1,d1 ,a1 < c1 。
简化前:线段a1b1和c1d1是否重叠。
简化后:线程c1d1和a1b1是否重叠。
两种显然等效。

简化二证明:

某组数a1,b1,c1,d1 a1 > b1。
线段a1b1就是b1a1,c1d1就是d1c1,所以无需证明。

重新简化

a<b 且b < c 且c<d。
ac的长度+bd的长度== ad的长度+bc的长度,都是ad的长度+bc的长度。
故调整a、b,使得a<b。调整c、d,使得c<d。
调整后增加的长度就是:(c-b)*2,结果为负数忽略。

代码

template<class ELE,class ELE2>
void MinSelf(ELE* seft, const ELE2& other)
{*seft = min(*seft,(ELE) other);
}template<class ELE>
void MaxSelf(ELE* seft, const ELE& other)
{*seft = max(*seft, other);
}#define MacEnumMask(mask,maskMax) for (int mask = maskMax; mask; mask = (mask - 1) & maskMax) class Solution {
public:int maxValueAfterReverse(vector<int>& nums) {m_c = nums.size();long long ans = 0;for (int i = 0; i + 1 < m_c; i++){ans += abs(nums[i] - nums[i + 1]);}int iAdd = 0;for (int i = 1; i < m_c; i++){//交换nums[i,m_c)MaxSelf(&iAdd, abs(nums.back() - nums[i - 1]) - abs(nums[i] - nums[i - 1]));}for (int i = 1; i < m_c; i++){//交换nums[0,i)MaxSelf(&iAdd, abs(nums.front() - nums[i]) - abs(nums[i] - nums[i - 1]));}{//a,b在前 ,c,d在后int  b = max(nums[0], nums[1]);for (int j = 2; j < m_c; j++){int c = min(nums[j - 1], nums[j]);int d = max(nums[j - 1], nums[j]);MaxSelf(&iAdd, 2 * c - 2 * b);MinSelf(&b, d);}}{//c,d在前 ,a,b在后int b = max(nums[m_c-1], nums[m_c-2]);for (int j = m_c-2; j >0 ; j--){int c = min(nums[j - 1], nums[j]);int d = max(nums[j - 1], nums[j]);MaxSelf(&iAdd, 2 * c - 2 * b);MinSelf(&b, d);}}return ans + iAdd;}int m_c;
};

测试用例

template<class T,class T2>
void Assert(const T& t1, const T2& t2)
{assert(t1 == t2);
}template<class T>
void Assert(const vector<T>& v1, const vector<T>& v2)
{if (v1.size() != v2.size()){assert(false);return;}for (int i = 0; i < v1.size(); i++){Assert(v1[i], v2[i]);}}int main()
{vector<int> nums;{Solution sln;nums = { 2,4,9,24,2,1,10 };auto res = sln.maxValueAfterReverse(nums);Assert(68, res);}{Solution sln;nums = { 2, 3, 1, 5, 4 };auto res = sln.maxValueAfterReverse(nums);Assert(10, res);}}

2023年5月

class Solution {
public:
int maxValueAfterReverse(vector& nums) {
m_c = nums.size();
int iTotal = 0;
for (int i = 0; i + 1 < m_c; i++)
{
iTotal += abs(nums[i] - nums[i + 1]);
}
//长度为1的子数组,结构不变。翻转整个数组结果不变
int iMaxAdd = 0;
//处理以索引0开头或m_c-1结尾的子数组
for (int i = 0; i + 1 < m_c; i++)
{
//翻转[0,i]
const int iLeft = abs(nums[i + 1] - nums[0]) - abs(nums[i + 1] - nums[i]);
//翻转[i+1,m_c)
const int iRight = abs(nums.back() - nums[i]) - abs(nums[i + 1] - nums[i]);
iMaxAdd = max(iMaxAdd, iLeft);
iMaxAdd = max(iMaxAdd, iRight);
}
int iMaxC = INT_MIN, iMinB = INT_MAX;
for (int i = 0; i + 1 < m_c; i++)
{
const int& x = nums[i];
const int& y = nums[i + 1];
iMaxC = max(iMaxC, min(x, y));
iMinB = min(iMinB, max(x, y));
}
iMaxAdd = max(iMaxAdd, 2 * (iMaxC - iMinB));
return iTotal + iMaxAdd;
}
int m_c;
};

扩展阅读

视频课程

有效学习:明确的目标 及时的反馈 拉伸区(难度合适),可以先学简单的课程,请移步CSDN学院,听白银讲师(也就是鄙人)的讲解。
https://edu.csdn.net/course/detail/38771

如何你想快速形成战斗了,为老板分忧,请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176

相关

下载

想高屋建瓴的学习算法,请下载《喜缺全书算法册》doc版
https://download.csdn.net/download/he_zhidan/88348653

我想对大家说的话
闻缺陷则喜是一个美好的愿望,早发现问题,早修改问题,给老板节约钱。
子墨子言之:事无终始,无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙,那算法就是他的是睛

测试环境

操作系统:win7 开发环境: VS2019 C++17
或者 操作系统:win10 开发环境: VS2022 C++17
如无特殊说明,本算法用**C++**实现。

这篇关于【分类讨论】【解析几何】【 数学】【推荐】1330. 翻转子数组得到最大的数组值的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!


原文地址:
http://www.chinasem.cn/article/812852

相关文章

MySQL JSON 查询中的对象与数组技巧及查询示例

《MySQLJSON查询中的对象与数组技巧及查询示例》MySQL中JSON对象和JSON数组查询的详细介绍及带有WHERE条件的查询示例,本文给大家介绍的非常详细,mysqljson查询示例相关知... 目录jsON 对象查询1. JSON_CONTAINS2. JSON_EXTRACT3. JSON_TA

Java SWT库详解与安装指南(最新推荐)

《JavaSWT库详解与安装指南(最新推荐)》:本文主要介绍JavaSWT库详解与安装指南,在本章中,我们介绍了如何下载、安装SWTJAR包,并详述了在Eclipse以及命令行环境中配置Java... 目录1. Java SWT类库概述2. SWT与AWT和Swing的区别2.1 历史背景与设计理念2.1.

Java日期类详解(最新推荐)

《Java日期类详解(最新推荐)》早期版本主要使用java.util.Date、java.util.Calendar等类,Java8及以后引入了新的日期和时间API(JSR310),包含在ja... 目录旧的日期时间API新的日期时间 API(Java 8+)获取时间戳时间计算与其他日期时间类型的转换Dur

MySQL 存储引擎 MyISAM详解(最新推荐)

《MySQL存储引擎MyISAM详解(最新推荐)》使用MyISAM存储引擎的表占用空间很小,但是由于使用表级锁定,所以限制了读/写操作的性能,通常用于中小型的Web应用和数据仓库配置中的只读或主要... 目录mysql 5.5 之前默认的存储引擎️‍一、MyISAM 存储引擎的特性️‍二、MyISAM 的主

C++ HTTP框架推荐(特点及优势)

《C++HTTP框架推荐(特点及优势)》:本文主要介绍C++HTTP框架推荐的相关资料,本文通过实例代码给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录1. Crow2. Drogon3. Pistache4. cpp-httplib5. Beast (Boos

JAVA数组中五种常见排序方法整理汇总

《JAVA数组中五种常见排序方法整理汇总》本文给大家分享五种常用的Java数组排序方法整理,每种方法结合示例代码给大家介绍的非常详细,感兴趣的朋友跟随小编一起看看吧... 目录前言:法一:Arrays.sort()法二:冒泡排序法三:选择排序法四:反转排序法五:直接插入排序前言:几种常用的Java数组排序

Python多进程、多线程、协程典型示例解析(最新推荐)

《Python多进程、多线程、协程典型示例解析(最新推荐)》:本文主要介绍Python多进程、多线程、协程典型示例解析(最新推荐),本文通过实例代码给大家介绍的非常详细,对大家的学习或工作具有一定... 目录一、multiprocessing(多进程)1. 模块简介2. 案例详解:并行计算平方和3. 实现逻

Spring Boot集成SLF4j从基础到高级实践(最新推荐)

《SpringBoot集成SLF4j从基础到高级实践(最新推荐)》SLF4j(SimpleLoggingFacadeforJava)是一个日志门面(Facade),不是具体的日志实现,这篇文章主要介... 目录一、日志框架概述与SLF4j简介1.1 为什么需要日志框架1.2 主流日志框架对比1.3 SLF4

Springboot实现推荐系统的协同过滤算法

《Springboot实现推荐系统的协同过滤算法》协同过滤算法是一种在推荐系统中广泛使用的算法,用于预测用户对物品(如商品、电影、音乐等)的偏好,从而实现个性化推荐,下面给大家介绍Springboot... 目录前言基本原理 算法分类 计算方法应用场景 代码实现 前言协同过滤算法(Collaborativ

Maven中引入 springboot 相关依赖的方式(最新推荐)

《Maven中引入springboot相关依赖的方式(最新推荐)》:本文主要介绍Maven中引入springboot相关依赖的方式(最新推荐),本文给大家介绍的非常详细,对大家的学习或工作具有... 目录Maven中引入 springboot 相关依赖的方式1. 不使用版本管理(不推荐)2、使用版本管理(推