3381. Maximum Subarray Sum With Length Divisible by K

[mah-shamim]

Topics: Array, Hash Table, Prefix Sum, Weekly Contest 427

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 * 10⁵
• -10⁹ <= nums[i] <= 10⁹

Hint:

1. Maintain minimum prefix sum ending at every possible index%k.

Footnotes

1. Subarray: A subarray is a contiguous non-empty sequence of elements within an array. ↩

[mah-shamim]

We have two prefix sums at indices i and j where (i % k) == (j % k), then the subarray from i+1 to j has length (j - i) which is divisible by k. This is because:

• i % k == j % k implies (j - i) % k == 0

Approach:

• Prefix Sum Technique: Calculate cumulative sums while iterating through the array
• Modulo Tracking: Use the remainder when dividing indices by k to group positions
• Minimum Prefix Storage: Maintain the smallest prefix sum for each modulo group
• Subarray Length Control: Ensure subarray length is divisible by k through modulo arithmetic
• Optimal Update Strategy: Update answer by comparing current prefix minus minimum prefix in same modulo group

Let's implement this solution in PHP: 3381. Maximum Subarray Sum With Length Divisible by K

<?php
/**
 * @param Integer[] $nums
 * @param Integer $k
 * @return Integer
 */
function maxSubarraySum($nums, $k) {
    $ans = PHP_INT_MIN;
    $prefix = 0;

    // minPrefix[i % k] := the minimum prefix sum at position i % k
    $minPrefix = array_fill(0, $k, PHP_INT_MAX / 2);
    $minPrefix[($k - 1) % $k] = 0;

    for ($i = 0; $i < count($nums); $i++) {
        $prefix += $nums[$i];
        $mod = $i % $k;
        $ans = max($ans, $prefix - $minPrefix[$mod]);
        $minPrefix[$mod] = min($minPrefix[$mod], $prefix);
    }

    return $ans;
}

// Test cases
echo maxSubarraySum([1,2], 1) . "\n";               // Output: 3
echo maxSubarraySum([-1,-2,-3,-4,-5], 4) . "\n";    // Output: -10
echo maxSubarraySum([-5,1,2,-3,4], 2) . "\n";       // Output: 4
?>

Explanation:

• Prefix Sum Array: We compute running totals to efficiently calculate subarray sums
• Modulo Grouping: Positions with same i % k form valid subarray endpoints when paired
• Minimum Tracking: For each modulo group, store the smallest prefix sum encountered
• Subarray Validation: When (current_index - min_index) % k == 0, the subarray length is divisible by k
• Answer Calculation: Maximum sum = current prefix - minimum prefix in same modulo group

Complexity

• Time: O(n) - Single pass through the array
• Space: O(k) - Storage for k modulo groups regardless of input size

[topugit]

Thanks for solving the problem of "Maximum Subarray Sum With Length Divisible by K"

[mah-shamim]

Thanks