# Maximum Subarray Sum With Length Divisible by K
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/maximum-subarray-sum-with-length-divisible-by-k)
Canonical: https://scaleengineer.com/dsa/problems/maximum-subarray-sum-with-length-divisible-by-k
**Patterns:** [Prefix Sum](https://scaleengineer.com/dsa/patterns/prefix-sum)
**Data structures:** Array, Hash Table
---
## Problem
You are given an array of integers `nums` and an integer `k`.

Return the **maximum** sum of a subarray of `nums`, such that the size of the subarray is **divisible** by `k`.

**Example 1:**

**Input:** nums = \[1,2\], k = 1

**Output:** 3

**Explanation:**

The subarray `[1, 2]` with sum 3 has length equal to 2 which is divisible by 1.

**Example 2:**

**Input:** nums = \[-1,-2,-3,-4,-5\], k = 4

**Output:** \-10

**Explanation:**

The maximum sum subarray is `[-1, -2, -3, -4]` which has length equal to 4 which is divisible by 4.

**Example 3:**

**Input:** nums = \[-5,1,2,-3,4\], k = 2

**Output:** 4

**Explanation:**

The maximum sum subarray is `[1, 2, -3, 4]` which has length equal to 4 which is divisible by 2.

**Constraints:**

* `1 <= k <= nums.length <= 2 * 105`
* `-109 <= nums[i] <= 109`

# Approaches
## Brute Force
The most straightforward approach is to check every possible subarray within the given array `nums`. We can generate all subarrays, and for each one, we check if its length is divisible by `k`. If it is, we calculate its sum and compare it with the maximum sum found so far.
**Time:** O(N²), where N is the length of the `nums` array. The two nested loops result in a quadratic number of operations. · **Space:** O(1), as we only use a few variables to store the running sum and the maximum sum.
**Pros:** Simple to understand and implement.; Requires minimal extra space.
**Cons:** This approach is too slow for large input arrays and will likely result in a 'Time Limit Exceeded' error on competitive programming platforms.
### Explanation
We can implement this using two nested loops. The outer loop iterates through all possible starting indices `i` of a subarray, and the inner loop iterates through all possible ending indices `j`. For each pair of `(i, j)`, we have a subarray `nums[i...j]`. We then check if its length, `j - i + 1`, is divisible by `k`. To avoid a third loop for calculating the sum, which would lead to an O(N³) complexity, we can maintain a running sum within the inner loop. We start with `currentSum = 0` for each starting index `i` and accumulate the values as `j` increases. Whenever the length condition is met, we update our global `maxSum`. Since the sum of elements can be large, we should use a `long` data type for sums. We initialize `maxSum` to a very small value to correctly handle cases where all subarray sums are negative.

```java
class Solution {
    public long maximumSubarraySum(int[] nums, int k) {
        int n = nums.length;
        long maxSum = Long.MIN_VALUE;
        boolean found = false;

        for (int i = 0; i < n; i++) {
            long currentSum = 0;
            for (int j = i; j < n; j++) {
                currentSum += nums[j];
                int length = j - i + 1;
                if (length > 0 && length % k == 0) {
                    found = true;
                    maxSum = Math.max(maxSum, currentSum);
                }
            }
        }

        // According to constraints, a valid subarray always exists.
        // If it didn't, returning 0 might be a sensible default.
        return found ? maxSum : 0;
    }
}
```
### Algorithm
*   Initialize `maxSum` to a very small number (e.g., `Long.MIN_VALUE`) and a boolean flag `found` to `false`.
*   Iterate through the array with an outer loop for the start index `i` from `0` to `n-1`.
*   Inside the outer loop, initialize a `currentSum` to `0`.
*   Start an inner loop for the end index `j` from `i` to `n-1`.
*   In the inner loop, add `nums[j]` to `currentSum`.
*   Calculate the length of the current subarray: `length = j - i + 1`.
*   If `length % k == 0`, it means we have found a valid subarray.
    *   Set `found` to `true`.
    *   Update `maxSum` by taking the maximum of the current `maxSum` and `currentSum`.
*   After the loops complete, if `found` is `true`, return `maxSum`. Otherwise, return `0`. (Note: The problem constraints `1 <= k <= nums.length` guarantee that at least one valid subarray exists, so `found` will always be true. Returning `maxSum` directly after initializing it to `Long.MIN_VALUE` is sufficient).

## Prefix Sum with Hashing
A much more efficient solution can be developed using prefix sums and modular arithmetic. The core idea is that the sum of a subarray `nums[i...j]` can be expressed as the difference between two prefix sums. The condition on the subarray's length can be translated into a condition on the indices of these prefix sums modulo `k`.
**Time:** O(N), where N is the length of `nums`. We iterate through the array only once, and hash map operations take, on average, O(1) time. · **Space:** O(k), where `k` is the given integer. We use a hash map (or an array of size `k`) to store one entry for each possible remainder modulo `k`.
**Pros:** Highly efficient with linear time complexity.; This is the optimal solution for the problem.
**Cons:** Requires understanding of prefix sums and modular arithmetic.; Space complexity is proportional to `k`, which can be large.
### Explanation
Let `P[x]` be the prefix sum of the first `x` elements of `nums`. The sum of a subarray from index `i` to `j` is `P[j+1] - P[i]`. The length of this subarray is `j - i + 1`. We are given that the length must be a multiple of `k`, so `(j - i + 1) % k == 0`. This simplifies to `(j + 1) % k == i % k`.

This transforms the problem into finding two prefix sum indices, say `p = j + 1` and `q = i`, such that `p % k == q % k` and the difference `P[p] - P[q]` is maximized. To maximize this difference for a given `p`, we need to subtract the smallest possible `P[q]` that we have encountered so far among all `q < p` that satisfy the remainder condition.

We can solve this by iterating through the array once while calculating the prefix sum. We use a hash map or an array of size `k` to keep track of the minimum prefix sum encountered for each remainder `r` from `0` to `k-1`. For each new prefix sum `P[p]`, we check our map for the minimum `P[q]` with the same remainder and update our `maxSum` if `P[p] - P[q]` is larger. Then, we update the map with the current `P[p]` if it's smaller than the existing minimum for its remainder.

```java
import java.util.Map;
import java.util.HashMap;

class Solution {
    public long maximumSubarraySum(int[] nums, int k) {
        int n = nums.length;
        Map<Integer, Long> minPrefixSumMap = new HashMap<>();
        // Base case: a prefix sum of 0 at index -1 (logically P[0])
        // The remainder of index 0 is 0 % k = 0.
        minPrefixSumMap.put(0, 0L);

        long currentPrefixSum = 0L;
        long maxSum = Long.MIN_VALUE;

        for (int i = 0; i < n; i++) {
            currentPrefixSum += nums[i];
            // The current prefix sum is P[i+1]. The index is i+1.
            int remainder = (i + 1) % k;

            if (minPrefixSumMap.containsKey(remainder)) {
                long prevMinSum = minPrefixSumMap.get(remainder);
                maxSum = Math.max(maxSum, currentPrefixSum - prevMinSum);
            }

            // Update the map with the minimum prefix sum for this remainder.
            minPrefixSumMap.put(remainder, Math.min(minPrefixSumMap.getOrDefault(remainder, Long.MAX_VALUE), currentPrefixSum));
        }

        // If maxSum was never updated, it means no valid subarray was found.
        // Per constraints, this won't happen. If it could, returning 0 would be a safe bet.
        return maxSum == Long.MIN_VALUE ? 0 : maxSum;
    }
}
```
### Algorithm
*   Let `P[x]` be the prefix sum `nums[0] + ... + nums[x-1]`, with `P[0] = 0`.
*   The sum of a subarray `nums[i...j]` is `P[j+1] - P[i]`.
*   The length of this subarray is `(j+1) - i`. We need this to be a multiple of `k`, which means `((j+1) - i) % k == 0`, or `(j+1) % k == i % k`.
*   The problem is now to find `max(P[p] - P[q])` for indices `p > q` where `p % k == q % k`.
*   To maximize `P[p] - P[q]` for a given `p`, we need to find the minimum `P[q]` for all `q < p` with the same remainder modulo `k`.
*   We can achieve this in a single pass:
    1.  Initialize `maxSum = Long.MIN_VALUE`.
    2.  Initialize a map or an array `minPrefixSum` to store the minimum prefix sum seen for each remainder modulo `k`. Initialize values to a large number.
    3.  Set `minPrefixSum[0] = 0` to account for the initial empty prefix (`P[0]=0`).
    4.  Initialize `currentPrefixSum = 0`.
    5.  Iterate through `nums` from `i = 0` to `n-1`:
        a.  Update `currentPrefixSum += nums[i]`. This sum represents `P[i+1]`.
        b.  Calculate the remainder `r = (i + 1) % k`.
        c.  Check if `minPrefixSum` has an entry for `r`. If it does, it means we've seen a previous prefix sum `P[q]` where `q % k == r`. The difference `currentPrefixSum - minPrefixSum[r]` is a candidate for the maximum sum.
        d.  Update `maxSum = max(maxSum, currentPrefixSum - minPrefixSum[r])`.
        e.  Update `minPrefixSum[r]` with the minimum value between its current value and `currentPrefixSum`.
*   Return `maxSum` (or 0 if no valid subarray is found, though constraints prevent this).

# Solutions
### Java

```java
class Solution {
public
  long maxSubarraySum(int[] nums, int k) {
    long[] f = new long[k];
    final long inf = 1L << 62;
    Arrays.fill(f, inf);
    f[k - 1] = 0;
    long s = 0;
    long ans = -inf;
    for (int i = 0; i < nums.length; ++i) {
      s += nums[i];
      ans = Math.max(ans, s - f[i % k]);
      f[i % k] = Math.min(f[i % k], s);
    }
    return ans;
  }
}
```

### CPP

```cpp
class Solution {
public:
  long long maxSubarraySum(vector<int> &nums, int k) {
    using ll = long long;
    ll inf = 1e18;
    vector<ll> f(k, inf);
    ll ans = -inf;
    ll s = 0;
    f[k - 1] = 0;
    for (int i = 0; i < nums.size(); ++i) {
      s += nums[i];
      ans = max(ans, s - f[i % k]);
      f[i % k] = min(f[i % k], s);
    }
    return ans;
  }
};
```

### Python

```python
class Solution:
    def maxSubarraySum(self, nums: List[int], k: int) -> int: f = [inf] * k ans = - inf s = f[- 1] = 0 for i, x in enumerate(nums): s += x ans = max(ans, s - f[i % k]) f[i % k] = min(f[i % k], s) return ans

```