3381. Maximum Subarray Sum With Length Divisible by K

Description

You are given an array of integers nums and an integer k.

Return the maximum sum of a 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

 

Solutions

Solution: Prefix Sum

• Time complexity: O(n)
• Space complexity: O(k)

 

JavaScript

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
const maxSubarraySum = function (nums, k) {
  const n = nums.length;
  const sums = Array.from({ length: k }, () => Number.MAX_SAFE_INTEGER);
  let prefixSum = 0;
  let result = Number.MIN_SAFE_INTEGER;

  sums[k - 1] = 0;

  for (let index = 0; index < n; index++) {
    prefixSum += nums[index];

    const pos = index % k;
    const sum = prefixSum - sums[pos];

    result = Math.max(sum, result);
    sums[pos] = Math.min(sums[pos], prefixSum);
  }

  return result;
};