最大信用問題 — 一個區段問題的例子
給定一個含數字的陣列 A [0.. N)
, 0 ≤ N
. 其中任一個連續區段 [p..q)
的「信用」是其中正數的個數減去負數的個數:
credit p q =〈# i : p ≤ i < q : A i > 0〉-
〈# i : p ≤ i < q : A i < 0〉
請推導出一個程式,計算該陣列中「信用最高的區段」的信用,也就是
〈↑ p q : 0 ≤ p ≤ q ≤ N : credit p q〉