配列 / 文字列（応用）累積和（Prefix Sum）

LeetCode 練習問題集

問題	難易度	重要度	テクニック
Running Sum of 1d Array	★	高	累積和
Maximum Score After Splitting a String	★★	高	累積和
Product of Array Except Self	★★★	高	累積和
Sum of Absolute Differences in a Sorted Array	★★★	高	累積和
Maximum Good Subarray Sum	★★★	高	累積和
Subarray Sum Equals K	★★★	中	累積和（ハッシュテーブル）
Subarray Sums Divisible by K	★★★	中	累積和（ハッシュテーブル）

累積和（Prefix Sum）とは事前に配列の総和を計算しておく事で任意の区間の和をO(1)で計算できるアルゴリズムです。例えば、任意の区間の和を計算するクエリを何度も呼び出す際に活用する事ができます。非常によく活用されるアルゴリズムです。部分配列の和と聞いたら真っ先に適用できないかを考えてみましょう。

Maximum subarray

難易度:★★ 重要度: 高