Scale Engineer

Maximum Subarray Sum With Length Divisible by K

Med
#3004Time: 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.
Patterns
Prefix Sum
Data structures
ArrayHash Table

Prompt

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

2 approaches with complexity analysis and trade-offs.

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.

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).

Walkthrough

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.

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;    }}

Complexity

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.

Trade-offs

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.

Solutions

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;  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem