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算法:前缀和、前缀乘积、前缀异或的原理、源码及测试用例:付视频课程 二分 过些天整理基础知识 题目 给定一个非负整数数组 nums 和一个整数 m ,你需要将这个数组分成 m 个非空的连续子数组。 设计一个算法…...
gitlab自编译 源码下载
网上都是怎么用 gitlab,但是实际开发中有需要针对 gitlab 进行二次编译自定义实现功能的想法。 搜索了网上的资料以及在官网的查找,查到了如下 gitlab 使用 ruby 开发。 gitlab 下载包 gitlab/gitlab-ce - Packages packages.gitlab.com gitlab/gitl…...
SBD(Schottky Barrier Diode)与JBS(Junction Barrier Schottky)
SBD和JBS二极管都是功率二极管,具有单向导电性,在电路中主要用于整流、箝位、续流等应用。两者的主要区别在于结构和性能。 结构 SBD是肖特基二极管的简称,其结构由一个金属和一个半导体形成的金属-半导体结构成。 JBS是结势垒肖特基二极…...
HANA:计算视图-图形化Aggregation组件-踩坑小记(注意事项)
今天遇到在做HANA视图开发的时候,遇到一个事,一直以为是个BUG,可把我气坏了,具体逻辑是这样的,是勇图形化处理的,ACDOCA innerjoin 一个时间维度表,就这么简单,完全按照ACDOCA的主键…...
【milkv】更新rndis驱动
问题 由于windows升级到了11,导致rndis驱动无法识别到。 解决 打开设备管理器,查看网络适配器,没有更新会显示黄色的图标。 右击选择更新驱动...
基于混沌博弈优化的BP神经网络(分类应用) - 附代码
基于混沌博弈优化的BP神经网络(分类应用) - 附代码 文章目录 基于混沌博弈优化的BP神经网络(分类应用) - 附代码1.鸢尾花iris数据介绍2.数据集整理3.混沌博弈优化BP神经网络3.1 BP神经网络参数设置3.2 混沌博弈算法应用 4.测试结果…...
基于人工水母优化的BP神经网络(分类应用) - 附代码
基于人工水母优化的BP神经网络(分类应用) - 附代码 文章目录 基于人工水母优化的BP神经网络(分类应用) - 附代码1.鸢尾花iris数据介绍2.数据集整理3.人工水母优化BP神经网络3.1 BP神经网络参数设置3.2 人工水母算法应用 4.测试结果…...
【C++】哈希学习
哈希学习 unordered系列关联式容器哈希结构除留余数法哈希冲突闭散列线性探测二次探测 负载因子开散列开散列增容 闭散列 VS 开散列字符串哈希算法 线性探测 & 二次探测实现拉链法实现 unordered系列关联式容器 unordered系列关联式容器是从C11开始,STL提供的。…...
Nginx的安装——window环境
1、下载Nginx 在官网下载稳定版本: http://nginx.org/en/download.html 以nginx/Windows-1.24.0为例,直接下载 nginx-1.24.0.zip。 下载后解压,解压后如下: 2、启动nginx 在window环境下启动nginx的方法有以下两种: …...
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)(二)】
列存储(CU)(二) 概述GetCUHeaderSize 函数Compress 函数CU::FillCompressBufHeader 函数CU::CompressNullBitmapIfNeed 函数CU::CompressData 函数 声明:本文的部分内容参考了他人的文章。在编写过程中,我们…...
Java并发面试题:(四)synchronized和lock区别
synchronized 关键字 synchronized关键字解决的是多个线程之间访问资源的同步性,synchronized关键字可以保证被它 修饰的方法或者代码块在任意时刻只能有一个线程执行。 另外,在 Java 早期版本中, synchronized属于重量级锁,效率…...
使用Nginx实现采集端和数据分析平台的数据加密传输
1. 需求描述 目前鸿鹄暴露出来的重要ports如下表: 在实际的生产环境中,结合我司的使用场景,需要在鸿鹄前端安装proxy,用以解决如下两个问题: 1.1 实现http到https的强制跳转 企业环境中,一般会关闭http 80端…...
appium---如何判断原生页面和H5页面
目前app中存在越来越多的H5页面了,对于一些做app自动化的测试来说,要求也越来越高,自动化不仅仅要支持原生页面,也要可以H5中进行操作自动化, webview是什么 webview是属于android中的一个控件,也相当于一…...
【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文件 要想写代码,你得有文件啊 以前的创建方式: 右键新建文本文档,开始写代码,写完改后缀名,保存……这样文件一旦多了…...
day36
今日内容概要 进程基础(操作系统中的概念) 进程调度算法(四种算法) 进程的并行和并发的概念 同步异步阻塞非阻塞的概念 创建进程(进程类Process) Process类的参数 Process类的方法 如何开启多进程 基于TCP协议的高并发程序 进程基础 进程它是操作系统中最重要的概念…...
五. 激光雷达建图和定位方案-开源SLAM
前面内容: 一. 器件选型心得(系统设计)--1_goldqiu的博客-CSDN博客 一. 器件选型心得(系统设计)--2_goldqiu的博客-CSDN博客 二. 多传感器时间同步方案(时序闭环)--1 三. 多传感器标定方案&a…...
SAP MM学习笔记37 - 请求书照合中的 追加请求/追加Credit 等概念/ 请求书的取消
有关请求书照合,之前学习了一部分,现在再来学其中的一些概念。 其实这些概念也许并不常用,但是你又不能不知道,因为客户会问。 有关请求书,贴一些以前学习的文章,以方便阅读。 SAP MM学习笔记33 - 请求书…...
【C#】Winform实现轮播图
复制后,需要修改的代码: 1、图片文件夹路劲:string folderPath "C:\\Users\\Administrator\\Desktop\\images"; 2、项目命名空间:namespace BuildAction 全窗口代码: using System; using System.Colle…...
MyBatisPlus(十九)自动填充
说明 自动填充指的是,当数据被 插入 或者 更新 的时候,会为指定字段进行一些默认的数据填充。 比如,插入时,会自动填充数据的创建时间和更新时间;更新时,会自动填充数据的更新时间。 实现方式 配置处理器…...
设计模式_命令模式
命令模式 介绍 定义案例问题堆积在哪里解决办法 行为形设计模式 就是把 “发布命令 执行命令”细化为多个角色 每个角色又能继续细化 发布命令 1 打印1-9 a 打印A-G 如果有更多的命令 命令处理方式更加多样性 更复杂 处理命令的顺序拆分角色:降低耦合度 命令类&am…...
python接口自动化测试(六)-unittest-单个用例管理
前面五节主要介绍了环境搭建和requests库的使用,可以使用这些进行接口请求的发送。但是如何管理接口案例?返回结果如何自动校验?这些内容光靠上面五节是不行的,因此从本节开始我们引入python单元测试框架 unittest,用它…...
tomcat 服务器
tomcat 服务器 tomcat: 是一个开源的web应用服务器。区别nginx,nginx主要处理静态页面,那么动态请求(连接数据库,动态页面)并不是nginx的长处,动态的请求会交给tomcat进行处理。 nginx-----转发动态请求-…...
如果你有一次自驾游的机会,你会如何准备?
常常想来一次说走就走的自驾游,但是光是想想就觉得麻烦的事情好多:漫长的公路缺少娱乐方式、偏僻拗口的景点地名难以导航、不熟悉的城市和道路容易违章…… 也因为如此,让我发现了HUAWEI HiCar这个驾驶人的宝藏! 用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? 经过我查阅多方资料,在网上看到一个比较合适的例子 地址…...
Go实现CORS(跨域)
引言 很多时候,需要允许Web应用程序在不同域之间(跨域)实现共享资源。本文将简介跨域、CORS的概念,以及如何在Golang中如何实现CORS。 什么是跨域 如果两个 URL 的协议、端口(如果有指定的话)和主机都相…...
第一章:变量和简单的数据类型
第一节 变量 variable(变量),每个变量指向一个值————与该变量相关联的信息 message"hello python world!" print(message) 1.1变量的命名和使用 1.变量名只能包含数字(0~9)、字母(Aa~Zz)和下划线(_)。变量可以使用字母和下划线作为开头,…...
【初识Linux】:常见指令(2)
朋友们、伙计们,我们又见面了,本期来给大家解读一下有关Linux的基础知识点,如果看完之后对你有一定的启发,那么请留下你的三连,祝大家心想事成! C 语 言 专 栏:C语言:从入门到精通 数…...
“torch.load“中出现的“Unexpected key(s) in state_dict“报错问题
问题: 解决: 添加strictFalse,允许加载过程中出现不匹配的键。但请注意,仍然需要确保模型中的主要参数能够正确加载,以确保模型的有效性。 model.load_state_dict(state_dict) # 改为: model.load_state_dict(state…...
个人做的网站能备案吗/汕头网站关键词推广
教育 教育 试卷代号:1079 2021年春季学期期末统一考试 高等代数专题研究 试题 2021年7月 一、单项选择题(本题共20分,每小题4分) 1.下列运算中,( )是有理数域Q上的代数运算. A.a。ba B.a。bb …...
云商城自助下单平台/百度seo推广软件
转载自:http://blog.csdn.net/jiuqiyuliang/article/details/8581803 为了描述系统实现方面的信息,使系统具有可重用性和可操作性的目的,构件图和部署图来表示实现单元。 1、构件 将系统中可重用的模块封装为具有可替代性的物理单元,称为构件…...
最优秀的无锡网站建设/竞价托管外包代运营
四叶玫瑰数 描述 四叶玫瑰数是4位数的自幂数。自幂数是指一个 n 位数,它的每个位上的数字的 n 次幂之和等于它本身。(例如:当n为3时,有1^3 5^3 3^3 153,153即是n为3时的一个自幂数,3位数的自幂数被称为…...
做公司网站别人能看到吗/深圳外贸seo
一、关于MySQL权限的几点常识: 1、MySQL的权限系统主要用来验证用户的操作权限。 2、在MySQL内部,权限信息存放在MySQL数据库的granttable里。当mysql启动后,granttable里的信息会写入内存。 3、MySQL 使用user name 加 host name 来作为标识…...
南宁网站优化排名推广/百度排行榜
从小学五年级入坑海贼 到如今工作,整整15年了。 昨晚睡前看了粉丝剪辑的一个海贼王视频 很感慨 难以想象一个20多岁的成年人 下了班 躺在自己不足20平米的宿舍里 看的热泪盈眶 我只能说一生无悔海贼迷。 当然我不像别的海贼迷,花钱买很多昂贵的手办&…...
可以做网站开个写手公司/网络营销做得比较好的企业
在写Python过程中,经常会遇到对象的拷贝,如果不理解浅拷贝和深拷贝的概念,你的代码就可能出现一些问题。所以,在这里按个人的理解谈谈它们之间的区别。一、赋值(assignment)在《Python FAQ1》一文中,对赋值已经讲的很清…...