USACO Sliver 第一章 前缀和

前缀和是一种计算数组的方法，其中每个元素都是从数组的开头开始累加的和。

计算前缀和的方法是从数组的第一个元素开始遍历，将每个元素与前面的所有元素相加，并将结果存储在新的数组中。例如，如果我们有一个数组 A = [1, 2, 3, 4, 5]，则它的前缀和数组为 P = [1, 3, 6, 10, 15]。

前缀和可以应用于许多算法问题，例如快速计算一个数组中的元素之和，找到一个数组中的最大子序列和等。

我们可以使用前缀和算法快速计算一个数组中的元素之和。例如，如果我们有一个数组 A = [1, 2, 3, 4, 5]，则它的前缀和数组为 P = [1, 3, 6, 10, 15]。要计算数组 A 中元素的和，我们只需要计算 P[4] - P[0] + A[0] = 15。

我们可以使用前缀和算法找到一个数组中的最大子序列和。例如，如果我们有一个数组 A = [-2, 1, -3, 4, -1, 2, 1, -5, 4]，则它的前缀和数组为 P = [-2, -1, -4, 0, -1, 1, 2, -3, 1]。我们可以使用以下公式计算最大子序列和：
max_sum = max(P[j] - P[i-1] for i in range(n) for j in range(i, n))

示例代码