Let \(DP[i]\) denote the maximum score you can get in the prefix \((A_1, ..., A_i)\). Also let \(P_i = (A_1 + ... + A_i) \pmod K\). Then, note that \(K | A_{j+1} + ... + A_i\) is equivalent to \(P_i = P_j\). Moreover, note that \(DP\) is nondecreasing (because if \(i > j\) we can simply use the partition for \((A_1, ..., A_j)\) and add the sequence \(S_k = (A_{j+1}, ..., A_i)\) at the end.

Thus, we have

\[DP[i] = \max(\max_{j < i} DP[j], \max_{P_i = P_j} DP[j] + 1) = \]

\[\max(DP[i-1], \max_{j < i, P_i = P_j} DP[j] + 1)\]

Now, for each \(0 \leq k < K\), we can store \(f[k] = \max_{j < i, P_j = k} DP[i]\) in a hash map (where \(f[k] = -1\) if there does not exist \(j < i\) such that \(P_j = k\)). Then, we have \(DP[i] = \max(DP[i-1], f[P_i]+1)\) and after computing \(DP[i]\) we update \(f[P_i] = DP[i]\). Initially we have \(f[0] = 0, f[i] = -1 \forall i >0\) and \(DP[0] = 0\). The overall time complexity is \(O(N)\).