当前位置: 首页 > news >正文

C++算法前缀和的应用:分割数组的最大值的原理、源码及测试用例

分割数组的最大值

相关知识点

C++算法:前缀和、前缀乘积、前缀异或的原理、源码及测试用例:付视频课程

二分 过些天整理基础知识

题目

给定一个非负整数数组 nums 和一个整数 m ,你需要将这个数组分成 m 个非空的连续子数组。
设计一个算法使得这 m 个子数组各自和的最大值最小。
示例 1:
输入:nums = [7,2,5,10,8], m = 2
输出:18
解释:
一共有四种方法将 nums 分割为 2 个子数组。
其中最好的方式是将其分为 [7,2,5] 和 [10,8] 。
因为此时这两个子数组各自的和的最大值为18,在所有情况中最小。
示例 2:
输入:nums = [1,2,3,4,5], m = 2
输出:9
示例 3:
输入:nums = [1,4,4], m = 3
输出:4
提示:

1 <= nums.length <= 1000
0 <= nums[i] <= 10^6
1 <= m <= min(50, nums.length)

解法一:暴力解法

时间复杂度O(nnm),n是nums的长度。vMaxSum共有m*n种状态,求每种状态需的时间复杂度是O(n)。vPreSum记录前缀和,vMaxSum[i][j] 记录将nums[0,j]分成i个子数组的最大和。j’取值范围[0,j),vMaxSum[i][j]就是所有max(vMaxSum[i-1][j’],vPreSum[j+1] - vPreSum[j’])的最小值。这个时间复杂度在通过和不通过的边缘。

解法二:滑动窗口

假定j的j1是x,则当j增加时,x不变或增加。 当j++,vMaxSum[i-1][j’]不变,vPreSum[j+1] - vPreSum[j’] 增加。下面用因果表来证明。令L(j,x)= vMaxSum[i-1][x] R(j,x) = vPreSum[j+1] - vPreSum[x] |。
如果L(j,x)<= R(j,x)。x减少后,左式减少或不变,右式增加或不变。i++后,右式变大或不变。所以x减少只会让右式变大或不变。而右式显然大于左式,所以减少左式不会减少最大值。

规章编号证明
假设一合适的j1就是x
假设二L(j,x)> R(j,x)
推论一假设一 假设二x–后,L变小,R变大。如果L(j,x-1) >= R(j,x-1),结合假设二,x-1比x更合适。与假设一矛盾。L(j,x-1) < R(j,x-1)]
推论二对于j+1,取x最大和为L(j,x)或R(j+1,x);取x-1,最大和为R(j+1,x-1)

代码

class Solution {
public:
int splitArray(vector& nums, int k) {
m_c = nums.size();
vector vPreSum(1);
for (const auto& n : nums)
{
vPreSum.emplace_back(n + vPreSum.back());
}
vector pre(m_c);
for (int i = 0; i < m_c; i++)
{
pre[i] = vPreSum[i + 1] - vPreSum[0];
}
for(int i = 1 ; i < k ; i++ )
{
vector dp(m_c,-1);
int k = i ;
for (int j = i; j < m_c; j++)
{
k–;
int iMax = INT_MAX;
#define MaxCro (max(pre[k], vPreSum[j + 1] - vPreSum[k+1]))
while ((k < j) && (MaxCro <= iMax))
{
iMax = MaxCro;
k++;
}
dp[j] = iMax;
}
pre.swap(dp);
}
return pre.back();
}
int m_c;
};

测试用例

template
void Assert(const vector& v1, const vector& v2)
{
if (v1.size() != v2.size())
{
assert(false);
return;
}
for (int i = 0; i < v1.size(); i++)
{
assert(v1[i] == v2[i]);
}
}

template
void Assert(const T& t1, const T& t2)
{
assert(t1 == t2);
}

int main()
{
vector nums = { 1,2,3,4,5,6 };
int k = 2;
auto res = Solution().splitArray(nums, k);
Assert(res, 11);

 nums = { 1, 0, 3, 3, 0, 6 };k = 2;res = Solution().splitArray(nums, k);
Assert(res, 7);nums = { 6,5,3,2,2,1 };
k = 5;
res = Solution().splitArray(nums, k);
Assert(res, 6);nums = { 1,0,3,3,0,1 };
k = 5;
res = Solution().splitArray(nums, k);
Assert(res, 3);//CConsole::Out(res);

}

2023年一月版:二分

class Solution {
public:
int splitArray(vector& nums, int k) {
int iMax = *std::max_element(nums.begin(), nums.end());
int iSum = std::accumulate(nums.begin(), nums.end(),0);

	 int left = iMax-1, right = iSum;while (left+1 < right){int iMid = (left + right) / 2;if (NeedK(nums, iMid) <= k){right = iMid;}else{left = iMid;}}return right;}int NeedK(const vector<int>& nums, int iMaxSum){int iNeedK = 1;int iSum = 0;for (const auto& n : nums){if (iSum + n > iMaxSum){iSum = n;iNeedK++;}else{iSum+=n;}}return iNeedK;}

};

2023年8月版也是二分

class Solution {
public:
int splitArray(vector& nums, int k) {
int iSum = std::accumulate(nums.begin(), nums.end(), 0);
int left = -1, r = iSum;
while (r > left + 1)
{
const auto mid = left + (r - left) / 2;
if (Is(nums, mid, k))
{
r = mid;
}
else
{
left = mid;
}
}
return r;
}
bool Is(const vector& nums, const int iMaxSum, int k)
{
k–;//可以分配的新组
int iHas = 0;
for (const auto& n : nums)
{
iHas += n;
if (iHas > iMaxSum)
{
k–;
iHas = n;
if (n > iMaxSum)
{
return false;
}
}
}
return k >= 0;
}
};

扩展阅读

视频课程

有效学习:明确的目标 及时的反馈 拉伸区(难度合适),可以先学简单的课程,请移步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++算法前缀和的应用:分割数组的最大值的原理、源码及测试用例

分割数组的最大值 相关知识点 C算法&#xff1a;前缀和、前缀乘积、前缀异或的原理、源码及测试用例&#xff1a;付视频课程 二分 过些天整理基础知识 题目 给定一个非负整数数组 nums 和一个整数 m &#xff0c;你需要将这个数组分成 m 个非空的连续子数组。 设计一个算法…...

gitlab自编译 源码下载

网上都是怎么用 gitlab&#xff0c;但是实际开发中有需要针对 gitlab 进行二次编译自定义实现功能的想法。 搜索了网上的资料以及在官网的查找&#xff0c;查到了如下 gitlab 使用 ruby 开发。 gitlab 下载包 gitlab/gitlab-ce - Packages packages.gitlab.com gitlab/gitl…...

SBD(Schottky Barrier Diode)与JBS(Junction Barrier Schottky)

SBD和JBS二极管都是功率二极管&#xff0c;具有单向导电性&#xff0c;在电路中主要用于整流、箝位、续流等应用。两者的主要区别在于结构和性能。 结构 SBD是肖特基二极管的简称&#xff0c;其结构由一个金属和一个半导体形成的金属-半导体结构成。 JBS是结势垒肖特基二极…...

HANA:计算视图-图形化Aggregation组件-踩坑小记(注意事项)

今天遇到在做HANA视图开发的时候&#xff0c;遇到一个事&#xff0c;一直以为是个BUG&#xff0c;可把我气坏了&#xff0c;具体逻辑是这样的&#xff0c;是勇图形化处理的&#xff0c;ACDOCA innerjoin 一个时间维度表&#xff0c;就这么简单&#xff0c;完全按照ACDOCA的主键…...

【milkv】更新rndis驱动

问题 由于windows升级到了11&#xff0c;导致rndis驱动无法识别到。 解决 打开设备管理器&#xff0c;查看网络适配器&#xff0c;没有更新会显示黄色的图标。 右击选择更新驱动...

基于混沌博弈优化的BP神经网络(分类应用) - 附代码

基于混沌博弈优化的BP神经网络&#xff08;分类应用&#xff09; - 附代码 文章目录 基于混沌博弈优化的BP神经网络&#xff08;分类应用&#xff09; - 附代码1.鸢尾花iris数据介绍2.数据集整理3.混沌博弈优化BP神经网络3.1 BP神经网络参数设置3.2 混沌博弈算法应用 4.测试结果…...

基于人工水母优化的BP神经网络(分类应用) - 附代码

基于人工水母优化的BP神经网络&#xff08;分类应用&#xff09; - 附代码 文章目录 基于人工水母优化的BP神经网络&#xff08;分类应用&#xff09; - 附代码1.鸢尾花iris数据介绍2.数据集整理3.人工水母优化BP神经网络3.1 BP神经网络参数设置3.2 人工水母算法应用 4.测试结果…...

【C++】哈希学习

哈希学习 unordered系列关联式容器哈希结构除留余数法哈希冲突闭散列线性探测二次探测 负载因子开散列开散列增容 闭散列 VS 开散列字符串哈希算法 线性探测 & 二次探测实现拉链法实现 unordered系列关联式容器 unordered系列关联式容器是从C11开始&#xff0c;STL提供的。…...

Nginx的安装——window环境

1、下载Nginx 在官网下载稳定版本&#xff1a; http://nginx.org/en/download.html 以nginx/Windows-1.24.0为例&#xff0c;直接下载 nginx-1.24.0.zip。 下载后解压&#xff0c;解压后如下&#xff1a; 2、启动nginx 在window环境下启动nginx的方法有以下两种&#xff1a; …...

C语言笔记之指针

一.指针含义 1.a、*a与&a的区别 a存储指向变量的地址,*a为指针的值,&a为指针的地址 #include <stdio.h>int main(){/** 测试代码部分一 **/int a12;int *b1;b1&a1;printf(" a1 %d, &a1 %d, b1 %d, *b1 %d, &b1 %d\n\n",a1,&a1…...

【 OpenGauss源码学习 —— 列存储(CU)(二)】

列存储&#xff08;CU&#xff09;&#xff08;二&#xff09; 概述GetCUHeaderSize 函数Compress 函数CU::FillCompressBufHeader 函数CU::CompressNullBitmapIfNeed 函数CU::CompressData 函数 声明&#xff1a;本文的部分内容参考了他人的文章。在编写过程中&#xff0c;我们…...

Java并发面试题:(四)synchronized和lock区别

synchronized 关键字 synchronized关键字解决的是多个线程之间访问资源的同步性&#xff0c;synchronized关键字可以保证被它 修饰的方法或者代码块在任意时刻只能有一个线程执行。 另外&#xff0c;在 Java 早期版本中&#xff0c; synchronized属于重量级锁&#xff0c;效率…...

使用Nginx实现采集端和数据分析平台的数据加密传输

1. 需求描述 目前鸿鹄暴露出来的重要ports如下表&#xff1a; 在实际的生产环境中&#xff0c;结合我司的使用场景&#xff0c;需要在鸿鹄前端安装proxy&#xff0c;用以解决如下两个问题&#xff1a; 1.1 实现http到https的强制跳转 企业环境中&#xff0c;一般会关闭http 80端…...

appium---如何判断原生页面和H5页面

目前app中存在越来越多的H5页面了&#xff0c;对于一些做app自动化的测试来说&#xff0c;要求也越来越高&#xff0c;自动化不仅仅要支持原生页面&#xff0c;也要可以H5中进行操作自动化&#xff0c; webview是什么 webview是属于android中的一个控件&#xff0c;也相当于一…...

【WIFI】【WPS】如何从log角度判断WPS 已经连接上

在Android项目中,由于WPS在Framework 接口中已经remove了 只能通过wpa-supplicant 代码中去判断是否连接上了 这段代码log 表示 PBC模式下没有激活 09-21 22:42:16.221503 3782 3782 D wpa_supplicant: wlan0: 0: 04:cf:4b:21:a0:3e ssid=Openwrt-WPS-tp wpa_ie_len=0 rsn…...

[正式学习java①]——java项目结构,定义类和创建对象,一个标准javabean的书写

目录 一、创建第一个java文件 二、 初始类和对象 三、符合javabean规范的类 一、创建第一个java文件 要想写代码&#xff0c;你得有文件啊 以前的创建方式&#xff1a; 右键新建文本文档&#xff0c;开始写代码&#xff0c;写完改后缀名&#xff0c;保存……这样文件一旦多了…...

day36

今日内容概要 进程基础(操作系统中的概念) 进程调度算法(四种算法) 进程的并行和并发的概念 同步异步阻塞非阻塞的概念 创建进程(进程类Process) Process类的参数 Process类的方法 如何开启多进程 基于TCP协议的高并发程序 进程基础 进程它是操作系统中最重要的概念…...

五. 激光雷达建图和定位方案-开源SLAM

前面内容&#xff1a; 一. 器件选型心得&#xff08;系统设计&#xff09;--1_goldqiu的博客-CSDN博客 一. 器件选型心得&#xff08;系统设计&#xff09;--2_goldqiu的博客-CSDN博客 二. 多传感器时间同步方案&#xff08;时序闭环&#xff09;--1 三. 多传感器标定方案&a…...

SAP MM学习笔记37 - 请求书照合中的 追加请求/追加Credit 等概念/ 请求书的取消

有关请求书照合&#xff0c;之前学习了一部分&#xff0c;现在再来学其中的一些概念。 其实这些概念也许并不常用&#xff0c;但是你又不能不知道&#xff0c;因为客户会问。 有关请求书&#xff0c;贴一些以前学习的文章&#xff0c;以方便阅读。 SAP MM学习笔记33 - 请求书…...

【C#】Winform实现轮播图

复制后&#xff0c;需要修改的代码&#xff1a; 1、图片文件夹路劲&#xff1a;string folderPath "C:\\Users\\Administrator\\Desktop\\images"; 2、项目命名空间&#xff1a;namespace BuildAction 全窗口代码&#xff1a; using System; using System.Colle…...

MyBatisPlus(十九)自动填充

说明 自动填充指的是&#xff0c;当数据被 插入 或者 更新 的时候&#xff0c;会为指定字段进行一些默认的数据填充。 比如&#xff0c;插入时&#xff0c;会自动填充数据的创建时间和更新时间&#xff1b;更新时&#xff0c;会自动填充数据的更新时间。 实现方式 配置处理器…...

设计模式_命令模式

命令模式 介绍 定义案例问题堆积在哪里解决办法 行为形设计模式 就是把 “发布命令 执行命令”细化为多个角色 每个角色又能继续细化 发布命令 1 打印1-9 a 打印A-G 如果有更多的命令 命令处理方式更加多样性 更复杂 处理命令的顺序拆分角色&#xff1a;降低耦合度 命令类&am…...

python接口自动化测试(六)-unittest-单个用例管理

前面五节主要介绍了环境搭建和requests库的使用&#xff0c;可以使用这些进行接口请求的发送。但是如何管理接口案例&#xff1f;返回结果如何自动校验&#xff1f;这些内容光靠上面五节是不行的&#xff0c;因此从本节开始我们引入python单元测试框架 unittest&#xff0c;用它…...

tomcat 服务器

tomcat 服务器 tomcat: 是一个开源的web应用服务器。区别nginx&#xff0c;nginx主要处理静态页面&#xff0c;那么动态请求&#xff08;连接数据库&#xff0c;动态页面&#xff09;并不是nginx的长处&#xff0c;动态的请求会交给tomcat进行处理。 nginx-----转发动态请求-…...

如果你有一次自驾游的机会,你会如何准备?

常常想来一次说走就走的自驾游&#xff0c;但是光是想想就觉得麻烦的事情好多&#xff1a;漫长的公路缺少娱乐方式、偏僻拗口的景点地名难以导航、不熟悉的城市和道路容易违章…… 也因为如此&#xff0c;让我发现了HUAWEI HiCar这个驾驶人的宝藏&#xff01; 用HUAWEI HiCar…...

关于ts的keyof

type props_type {name: string,age: number }const props: props_type {name: tjq,age: 18 }for (const key in props) { //props[key]出现红色波浪线const value props[key]; }why&#xff1f; 经过我查阅多方资料&#xff0c;在网上看到一个比较合适的例子 地址&#xf…...

Go实现CORS(跨域)

引言 很多时候&#xff0c;需要允许Web应用程序在不同域之间&#xff08;跨域&#xff09;实现共享资源。本文将简介跨域、CORS的概念&#xff0c;以及如何在Golang中如何实现CORS。 什么是跨域 如果两个 URL 的协议、端口&#xff08;如果有指定的话&#xff09;和主机都相…...

第一章:变量和简单的数据类型

第一节 变量 variable(变量)&#xff0c;每个变量指向一个值————与该变量相关联的信息 message"hello python world!" print(message) 1.1变量的命名和使用 1.变量名只能包含数字(0~9)、字母(Aa~Zz)和下划线(_)。变量可以使用字母和下划线作为开头&#xff0c…...

【初识Linux】:常见指令(2)

朋友们、伙计们&#xff0c;我们又见面了&#xff0c;本期来给大家解读一下有关Linux的基础知识点&#xff0c;如果看完之后对你有一定的启发&#xff0c;那么请留下你的三连&#xff0c;祝大家心想事成&#xff01; C 语 言 专 栏&#xff1a;C语言&#xff1a;从入门到精通 数…...

“torch.load“中出现的“Unexpected key(s) in state_dict“报错问题

问题&#xff1a; 解决&#xff1a; 添加strictFalse&#xff0c;允许加载过程中出现不匹配的键。但请注意,仍然需要确保模型中的主要参数能够正确加载&#xff0c;以确保模型的有效性。 model.load_state_dict(state_dict) # 改为&#xff1a; model.load_state_dict(state…...

wordpress 魔/推广渠道有哪些

教学反思&#xff1a;三角形的中线与面积法人教版数学八年级上册第11章第1.2节《三角形的高、中线与角平分线》中&#xff0c;我们对三角形的中线描述是“连接三角形顶点和对边中点的线段”&#xff0c;这和前一小节中对边、对角概念的理解提出的要求对应&#xff0c;即学生能识…...

网站建设运营的灵魂是什么/网站关键字排名优化

lambda 传递ref参数有个语法bug&#xff0c;必须要显式书写参数类型。 //如 delegate bool FuncType(ref int num);FuncType func1; func1 num > true; //错 func1 (ref num) > true;//错 func1 (ref int num) > true;//ok//并且,当一个参数书写类型&#xff0c;其…...

越秀区建设局网站/三只松鼠搜索引擎营销案例

接口自动化大牛养成记 对于大多数未做过接口测试的同学来说&#xff0c;可能并不清楚接口到底是什么&#xff0c;甚至你去问很多做过接口测试的同学什么是接口&#xff0c;他们也说不出个所以然&#xff0c; 大多数人可能知道接口大概是什么&#xff0c;也知道怎么测&#xf…...

俄罗斯外贸常用网站/h5制作

控制标注哪些要素若要更精确地控制标注哪些要素和标注放置位置&#xff0c;您需要使用更高级的标注属性。具体而言&#xff0c;您可以调整标注哪些要素以及标注相对于要素的放置位置。有四种方法可控制需要标注哪些要素&#xff1a;1.设置控制标注在地图上放置顺序的标注优先级…...

扬州建设集团招聘信息网站/潍坊网站排名提升

1.起源——欧拉公式 &#xff0c;i是什么&#xff0c;欧拉公式在复平面的意义。eix其实构成了完备的标准正交基。 i代表了旋转。 欧拉恒等式在数学中严谨可以用泰勒公式推导得出&#xff0c;由eix和sinx cosx的泰勒展开可得。 eix可以理解为一个单位圆。并且很容易看出&#xf…...

360度网站模板/北京搜索引擎优化管理专员

我有大约10GB的pcap数据和IPv6流量,用于分析存储在IPv6头和其他扩展头中的信息.为此,我决定使用Scapy框架.我尝试了rdpcap函数,但是对于如此大的文件,不建议这样做.它试图将所有文件加载到内存中并卡在我的情况下.我在网上发现在这种情况下建议使用嗅探器,我的代码如下所示&…...