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 \pmod K~.

$$\displaystyle dp[i] = \begin{cases} \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{cases}$$

The answer will be

$$\displaystyle \max_{i=0}^N \left(\sum_{j=1}^i a_j - dp[i]\right)$$

Time Complexity: ~\mathcal O(N)~