Brief description:

序列 a 的 l, r 之间的最大子段和 (Maximum subsequence sum) 定义为：
Query(l, r) = Max {a[i]+a[i+1]+…+a[j] ; l ≤ i ≤ j ≤ r}.

GSS 系列是 SPOj 上的一组数据结构习题，一共 6 题，大部分是和最大字段和有关。

GSS1: 只有询问。GSS3：单点修改。
GSS5: 询问时，限定区间两端点 i, j 的取值范围。
GSS2、GSS4：相对的独立问题。。
GSS6: 加入插入和删除操作。
GSS7: 树上 GSS 问题。

Analysis:

…

Level 1.
GSS1 / GSS3 / GSS5

Level 2.
GSS4 / GSS2

Level 3.
GSS6 / GSS7

External link:

http://www.spoj.pl/problems/GSS1/
http://www.spoj.pl/problems/GSS2/
http://www.spoj.pl/problems/GSS3/
http://www.spoj.pl/problems/GSS4/
http://www.spoj.pl/problems/GSS5/
http://www.spoj.pl/problems/GSS6/
http://www.spoj.pl/problems/GSS7/

Posted by xiaodao
Category: 快晴