只是来扣个字眼
在百度百科上,关于最大子段和的定义,它是这么说的:
Max{0,a[i]+a[i+1]+…+a[j]},1<=i<=j<=n
那么,看到 GSS1,说让我们求一个最大子权和,和最大子段和的区别在于它不和 0 取 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);