Maximum Subarray Sum With Length Divisible by K

Maximum Subarray Sum With Length Divisible by K - 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.

A subarray is a contiguous non-empty sequence of elements within an array.

Input & Output

Example 1 — Basic Case

$ Input: nums = [1,-3,2,1,-1], k = 2

› Output: 3

💡 Note: Subarray [2,1] has length 2 (divisible by k=2) and sum 2+1=3, which is the maximum possible.

Example 2 — Longer Subarray

$ Input: nums = [-1,-2,0,2], k = 2

› Output: 2

💡 Note: Subarray [0,2] has length 2 (divisible by k=2) and sum 0+2=2, which is the maximum.

Example 3 — All Elements

$ Input: nums = [1,2], k = 1

› Output: 3

💡 Note: Since k=1, any subarray length is divisible by k. The entire array [1,2] has sum 3.

Constraints

1 ≤ nums.length ≤ 10⁵
-10⁴ ≤ nums[i] ≤ 10⁴
1 ≤ k ≤ nums.length

Visualization

Tap to expand

Understanding the Visualization

Input

Array nums=[1,-3,2,1,-1] and k=2

Process

Find all subarrays with length divisible by k=2

Output

Maximum sum is 3 from subarray [2,1]

Key Takeaway

🎯 Key Insight: Use prefix sums and track remainders modulo k to efficiently find subarrays with length divisible by k

Asked in

G Google 45 a Amazon 32 M Microsoft 28

The key insight is to use prefix sums with modular arithmetic. Track the minimum prefix sum for each remainder when position is divided by k. When the same remainder appears again, we can form a subarray with length divisible by k. Best approach uses prefix sum tracking. Time: O(n), Space: O(k)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Check All Subarrays	O(n³)	O(1)	Check every possible subarray with length divisible by k
Prefix Sum with Modular Arithmetic	O(n)	O(k)	Use prefix sums and track remainders when divided by k

Brute Force - Check All Subarrays — Algorithm Steps

Iterate through all starting positions
For each start, try all ending positions
Check if subarray length is divisible by k
Calculate sum and track maximum

Visualization

Tap to expand

Step-by-Step Walkthrough

Generate Subarrays

Try all start-end position pairs

Filter by Length

Keep only subarrays with length % k == 0

Find Maximum

Calculate sum and track the maximum

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

int solution(int* nums, int numsSize, int k) {
    int maxSum = INT_MIN;
    
    // Try all possible starting positions
    for (int i = 0; i < numsSize; i++) {
        // Try all possible ending positions
        for (int j = i; j < numsSize; j++) {
            int length = j - i + 1;
            // Check if length is divisible by k
            if (length % k == 0) {
                // Calculate sum of subarray
                int currentSum = 0;
                for (int m = i; m <= j; m++) {
                    currentSum += nums[m];
                }
                if (currentSum > maxSum) {
                    maxSum = currentSum;
                }
            }
        }
    }
    
    return maxSum;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Parse array manually
    int nums[1000];
    int numsSize = 0;
    char* token = strtok(line, "[,]");
    while (token != NULL) {
        nums[numsSize++] = atoi(token);
        token = strtok(NULL, "[,]");
    }
    
    int k;
    scanf("%d", &k);
    
    int result = solution(nums, numsSize, k);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n³)

Triple nested loops: O(n²) pairs of start/end positions, O(n) to calculate each sum

⚠ Quadratic Growth

Space Complexity

O(1)

Only using variables to track current and maximum sum

✓ Linear Space

23.4K Views

Medium Frequency

~25 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Check All Subarrays — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler