最大 连续 和 问题。 给出 一个 长度 为 n 的 序列 A[1], A[2],…, A[n]， 求 最大 连续 和。 换句话说， 要求 找到 1 ≤ i ≤ j ≤ n， 使得 A[i] +…+A[j] 尽量 大。
C语言关键代码如下：
tot = 0;
best = A[1]; //初始 最大值
for (int i = 1; i <= n; i++) {for (int j = i; j <= n; j++){ //检查 连续 子 序列 A[ i],..., A[ j] int sum = 0; for (int k = i; k <= j; k++) { sum += A[ k]; tot++; } //累加 元素 和 if (sum > best) best = sum; //更新 最大值 }
}
Haskell代码：
sums [x] = [x]
sums (x:y:s) = x:sums (x+y:s)
tot s 0 j = s!!j
tot s i j = s!!j - s!!(i-1)
sumset s = [tot s i j | i <- [0.. length s - 1], j<-[i.. length s - 1]]
best s = maximum $ sumset $ sums s