---
type: slide
---

Problem Statement: Given an array $a$, find the maximum size subarray that has a sum that's a multiple of $7$.

---

Use prefix sums?

---

Let's say our desired range is $[l, r]$.
Then, $a_l + a_{l+1} + \dots + a_r$ must be a multiple of $7$.

---

Let's use prefix sums.
* If $p$ is the prefix sum of $a$, $p_{r} - p_{l-1}$ must be a multiple of 7.
* This also means that $p_{r}\mod 7 = p_{l-1}\pmod 7$.

---

If we want to maximize the size, which is $r-l+1$, we want to minimize $l$ and maximize $r$.

Thus, we just need to find the maximum and minimum $i$ and $j$ where $p_i\pmod 7$ have the same value as $p_j\pmod 7$ and take the maximum difference for each possible value mod $7$.