Maximum Subarray Sum With Length Divisible by K - Video Solutions

Problem Overview: Given an integer array and an integer k, compute the maximum possible sum of a subarray whose length is divisible by k. The constraint on length means if a subarray starts at index j and ends at i, the condition (i - j) % k == 0 must hold.

Approach 1: Brute Force Enumeration (O(n²) time, O(1) space)

Enumerate every possible subarray and compute its sum. While expanding a subarray from index i to j, track the current length. Whenever the length satisfies (j - i + 1) % k == 0, update the maximum sum. Prefix sums can slightly simplify the sum calculation, but the algorithm still checks all O(n²) ranges. This approach demonstrates the core condition on subarray length but becomes too slow when n grows beyond a few thousand.

Approach 2: Prefix Sum + Modulo Enumeration (O(n) time, O(k) space)

The key observation: if a subarray from j to i-1 has length divisible by k, then i % k == j % k. Build a prefix sum array where prefix[i] is the sum of the first i elements. The subarray sum becomes prefix[i] - prefix[j]. For each remainder r = i % k, track the smallest prefix sum previously seen at an index with the same remainder. When you revisit that remainder, compute prefix[i] - minPrefix[r] to get the best subarray ending at i whose length is divisible by k. Update the maximum and refresh the stored minimum prefix if the current one is smaller. This turns the problem into a single pass over the array with constant-time updates.

The data structure holding the minimum prefix per remainder can be a simple array of size k or a hash table. Each iteration performs constant work: compute the new prefix sum, check the remainder group, update the answer, and maintain the minimum prefix value.

This technique relies on the interaction between index arithmetic and cumulative sums. Similar patterns appear in many array problems where constraints apply to subarray length, parity, or divisibility.

Recommended for interviews: Prefix Sum + Modulo Enumeration. Interviewers expect you to move from the quadratic enumeration idea to the prefix-sum observation that indices with the same i % k form valid boundaries. The optimized solution runs in O(n) time and uses only O(k) additional space, showing both algorithmic insight and familiarity with prefix sum patterns.