Problem Description

You are given an array of integers nums and an integer k. You need to find the maximum sum of a subarray of nums, such that the size of this subarray is divisible by k.

Intuition

The problem requires us to not only find a subarray with a maximum sum but also ensure the subarray's length is divisible by k. To solve this, we use a prefix sum approach combined with modulus operation to maintain subarrays of specific lengths.

1. Prefix Sum and Modulus: We use prefix sums to efficiently compute sums of subarrays. By maintaining an array f where f[i] represents the minimum prefix sum seen so far whose index has a modulus i % k, we can check for subarrays ending at any position with the required length divisible by k.

2. Iterative Calculation: As we iterate through nums, we update s, which is the running prefix sum. For each element, we determine the potential maximum sum of a subarray ending at that element using the formula s - f[i % k]. This ensures that we consider only those subarrays whose length is divisible by k.

3. Update of Minimums: After evaluating the potential maximum for the current element, we update f[i % k] to ensure it holds the smallest prefix sum for its corresponding modulus, helping maintain the condition for subarray lengths.

This efficient strategy allows us to determine the required subarray using a single pass through nums, operating in linear time and space relative to the number of elements and the divisor k.

Learn more about Prefix Sum patterns.

Solution Approach

The solution employs a combination of prefix sums and modulus operations using an array to keep track of subarrays of certain lengths. Here's a step-by-step breakdown of the approach:

1. Initialization:

   • We start by initializing an array f of size k with all elements set to infinity (inf), except for f[k-1] which is set to 0. This array f is used to track the minimum prefix sum recorded for each modulus when the index is divided by k.
   • We also initialize ans with a very negative value (-inf) to ensure any valid subarray sum will replace it.
   • s is initialized to 0 to accumulate the running sum of the elements in nums.

2. Iterate Through nums:

   • For each element x in nums, update s to include the current element, so s += x.
   • Compute the current potential maximum subarray sum as s - f[i % k] and update ans if this value is greater.

3. Update Minimum Prefix Sums:

   • For maintaining the validity of the modulus condition, update f[i % k] as min(f[i % k], s) to ensure it retains the smallest prefix sum with the same modulus.
   • By the end of the iteration, ans accumulates the maximum sum of a subarray whose length is divisible by k.

The key operation here involves efficiently calculating the necessary subarray sums using a constant-time update on an array of size k.

Here's the core code integrated into this approach:

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

Example Walkthrough

Let's walk through the solution with a small example to illustrate the process:

Example: Consider nums = [3, -1, 2, 1, -4, 2, 6] and k = 3. We need to find the maximum sum of a subarray whose length is divisible by k.

Step 1: Initialization

• Initialize f = [inf, inf, 0] where k = 3 leads to this size, with f[2] set to 0 based on initial setup.
• Set ans = -inf to ensure a smaller value is replaced.
• Start with a running prefix sum s = 0.

Step 2: Iteration Over nums

• Iteration 1: x = 3

  • Update s = 0 + 3 = 3
  • Calculate potential maximum: s - f[0 % 3] = 3 - f[0] = 3 - inf = -inf (not useful)
  • Since no update to ans, consider minimum update: f[0] = min(inf, 3) = 3

• Iteration 2: x = -1

  • Update s = 3 - 1 = 2
  • Calculate potential maximum: s - f[1 % 3] = 2 - f[1] = 2 - inf = -inf
  • Update f[1] = min(inf, 2) = 2

• Iteration 3: x = 2

  • Update s = 2 + 2 = 4
  • Calculate potential maximum: s - f[2 % 3] = 4 - f[2] = 4 - 0 = 4
  • Update ans = max(-inf, 4) = 4
  • Update f[2] = min(0, 4) = 0

• Iteration 4: x = 1

  • Update s = 4 + 1 = 5
  • Calculate potential maximum: s - f[0 % 3] = 5 - f[0] = 5 - 3 = 2
  • ans remains 4. Update minimum: f[0] = min(3, 5) = 3

• Iteration 5: x = -4

  • Update s = 5 - 4 = 1
  • Calculate potential maximum: s - f[1 % 3] = 1 - f[1] = 1 - 2 = -1
  • ans remains 4. Update: f[1] = min(2, 1) = 1

• Iteration 6: x = 2

  • Update s = 1 + 2 = 3
  • Calculate potential maximum: s - f[2 % 3] = 3 - f[2] = 3 - 0 = 3
  • ans remains 4. Update: f[2] = min(0, 3) = 0

• Iteration 7: x = 6

  • Update s = 3 + 6 = 9
  • Calculate potential maximum: s - f[0 % 3] = 9 - f[0] = 9 - 3 = 6
  • Update ans = max(4, 6) = 6

Final Result: The maximum sum of a subarray with length divisible by 3 is 6.

Solution Implementation

Time and Space Complexity

The code iterates over the nums list once to compute the maximum subarray sum mod k. Therefore, the time complexity is O(n), where n is the length of the nums list. Each operation within the loop (addition, subtraction, modulo, max/min operations) happens in constant time.

For space complexity, it maintains an array f of size k to store the minimum prefix sums mod k. Thus, the space complexity is O(k).

Learn more about how to find time and space complexity quickly.