采用了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