首页 > 其他分享 >学习日记--分治(leetcode 53 最大子数组和)

学习日记--分治(leetcode 53 最大子数组和)

时间:2022-10-13 13:46:19浏览次数:56  
标签:Status struct rSum -- 53 int iSum lSum leetcode

采用了leetcode官方思路--分治

思路:

求区间内的最大子段和

struct Status {
    int lSum, rSum, mSum, iSum;
};/*结构体用法:struct 结构体名{
    结构体所包含的变量或数组
}; */
//这是一个定义了名叫Status的结构体,里面有四个变量,struct是一种数据类型,
//lSum、rSum、mSum、iSum都是Status类型
//定义了一个操作,格式类似于定义一个函数,不过返回值类型是struct ststus,平常见到的是int
struct Status pushUp(struct Status l, struct Status r) { int iSum = l.iSum + r.iSum;//[l,r]区间和等于以l为左端点的区间和加上以r为右端点的区间和 int lSum = fmax(l.lSum, l.iSum + r.lSum);//以 l为左端点的最大子段和,它要么等于「左子区间」的lSum,要么等于「左子区间」的 iSum (区间和)加上「右子区间」的 lSum,二者取大。
    int rSum = fmax(r.rSum, r.iSum + l.rSum);//以r为右端点的最大子段和,它要么等于「右子区间」的 rSum,要么等于「右子区间」的 iSum 加上「左子区间」的 rSum,二者取大。
    int mSum = fmax(fmax(l.mSum, r.mSum), l.rSum + r.lSum);//最大子段和,「左子区间」的 mSum 和 「右子区间」的 mSum 中的一个;它也可能跨越 m,可能是「左子区间」的 rSum 和 「右子区间」的 lSum 求和。三者取大。
    return (struct Status){lSum, rSum, mSum, iSum};
}
//定义了一个get函数,a表示数组,l是左端点,r是右端点
struct Status get(int* a, int l, int r) {//int* a:表示一个名叫a的数组 数组名本省就是指针。 if (l == r) { return (struct Status){a[l], a[l], a[l], a[l]}; } int m = (l + r) >> 1;//l+r的值右移1位,相当l+r的值除以2取整。 struct Status lSub = get(a, l, m);//左区间 struct Status rSub = get(a, m + 1, r);//右区间 return pushUp(lSub, rSub);//上面pushup函数返回左右端点 } int maxSubArray(int* nums, int numsSize) { return get(nums, 0, numsSize - 1).mSum;//获取get结构的msum变量(最大子段和) }

 

标签:Status,struct,rSum,--,53,int,iSum,lSum,leetcode
From: https://www.cnblogs.com/zhishiyigenicheng/p/16787882.html

相关文章

  • MySql多字段排序
    我们平常工作中需求可能会要求表格某些数据会挨一起的,这样比较好比较的,这个就涉及到了MySQL多列排序问题ORDERBYlcl.id,ldt.id,lpe.weight_max上面需要排序的列越往前......
  • 驱动开发:内核遍历进程VAD结构体
    在上一篇文章《驱动开发:内核中实现Dump进程转储》中我们实现了ARK工具的转存功能,本篇文章继续以内存为出发点介绍VAD结构,该结构的全程是VirtualAddressDescriptor即虚拟......
  • stat命令的实现-mystat
    stat命令的实现-mystat任务列表:提交学习stat(1)的截图man-k,grep-r的使用伪代码产品代码mystate.c,提交码云链接测试代码,mystat与stat(1)对比,提交截图1.提交学习......
  • python functools 模块
    pythonfunctools模块常见APIcmp_to_keycmp_to_key()是将比较函数转化为关键字函数。与使用接受关键字函数的方法一同使用,如(sorted(),min(),max()...),改函数主要......
  • PCA主成分分析原理与基础知识
    笔记的主要内容是PCA(主成分分析)原理和基本知识,相关数学原理和核心概念。什么是PCA分析?主成分分析(PCA,principalcomponentanalysis)是一种数学降维方法,利用正交......
  • Orcale体系结构
    Orcale数据库服务器结构图一、实例当数据库启动时,系统先启动实例,自动分配SGA,并启动Orcale的多个后台进程。内存区域和后台进程合称为一个Orcale实例。1.orcale进程......
  • 2021 ICPC 沈阳
    队里状态不是很好,就打了两个小时,算是复健场。赛时两题,补题补到四题。E-EdwardGaming,theChampion小评\(\mathcal{Consider\by\\pmb{Wida}}\),\(\mathcal{Sol......
  • 王阳明的心学是什么?
    王阳明是中国文化中的儒家大师,而且是属于那种站在顶峰上的大师,可以称之为全能型的思想家。相比于王阳明取得的赫赫战绩,王阳明为中华文化做出最大的贡献,是他创造了心学,在他......
  • 7天7项云服务 | 04-高可靠的云数据库Cloud DataBase
          在云端使用数据库,包括在云主机上自行搭建MySQL等数据库,对于个人网站或微型服务来说可以满足使用需求。稍微大些的应用需要考虑数据库实例的高可用、数据存储......
  • 砍柴农夫与放羊倌的聊天
            两个人一起聊天,一个是砍柴的农夫、一个是放羊倌,聊一天的结果是羊吃饱了放羊倌完成一天的任务,砍柴的农夫一无所获。    上海疫情已经经历了“第五波......