关于最大子段和与最大子权和
查看原帖
关于最大子段和与最大子权和
638084
szhqwq楼主2023/7/21 14:49

只是来扣个字眼

在百度百科上,关于最大子段和的定义,它是这么说的:

Max{0,a[i]+a[i+1]+…+a[j]},1<=i<=j<=n 

那么,看到 GSS1,说让我们求一个最大子权和,和最大子段和的区别在于它不和 00 取 max⁡\max。

但是在 GSS3 与 GSS5 中,虽然写的是最大子段和,但是,原题目是这样说的:

GSS3:

max{Ai + Ai+1 + .. + Aj | x<=i<=j<=y }

GSS5:

Max { A[i]+A[i+1]+...+A[j] ; x1 <= i <= y1 , x2 <= j <= y2 and x1 <= x2 , y1 <= y2 }

并且都没有像 GSS7 那样强调可以为空。

所以,我仅仅是想知道,究竟是题目有一点误区,还是说是我对于最大子段和与最大子权和的区别与定义有误。

可能会有人说我这么做并没有什么意义

另外,我的代码有一定证明性:

GSS3:

tr[u].val = tr[u].res = tr[u].suml = tr[u].sumr = a[l];

GSS7:

tr[u].val = a[l];
tr[u].res = tr[u].suml = tr[u].sumr = max(tr[u].val,0ll);
2023/7/21 14:49
加载中...