Subtask 1

We can simply loop over all $\mathcal{O}(N^2)$ subarrays and find the max sum of a subarray with size divisible by $K$. This can be done efficiently with a prefix sum array or sliding window.

Time Complexity: $\mathcal{O}(N^2)$

Subtask 2

This subtask was created to reward unoptimized solutions close to a full solution that ran in $\mathcal{O}(NK)$.

Subtask 3

We reduce the problem to $K$ instances of the classical maximal subarray problem. For each $1\le i\le K$, we will start from element $i$, constructing a new array of size $\mathcal{O}(\frac{N}{K})$ by compressing every subsequent block of $K$ elements into a single element with value equal to their sum; this can be done efficiently with a prefix sum array. Each subarray of this compressed array will correspond to a subarray of $a$ with size that is a multiple of $K$. Finding the maximal subarray over all $K$ compressed arrays, we arrive at our answer.

Time Complexity: $\mathcal{O}(N)$

Alternate solution

Another solution involves dynamic programming. We let $dp[i]$ be the minimum sum of a prefix $a_1,a_2,\dots ,a_j$ such that $j\le i$ and $j\equiv i(\mathrm{mod}K)$.

$${\displaystyle dp[i]=\{\begin{array}{ll}\sum _{j=1}^i{a}_j& 0\le i<K\\ min(dp[i-K],\sum _{j=1}^i{a}_j)& K\le i\le N\end{array}}$$

The answer will be

$${\displaystyle \underset{i=0}{\overset{N}{max}}(\sum _{j=1}^i{a}_j-dp[i])}$$

Time Complexity: $\mathcal{O}(N)$