3653. Maximum Subarray Sum With Length Divisible By K¶

Difficulty: Medium

3653. Maximum Subarray Sum With Length Divisible by K

Medium

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

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

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⁹

Solution¶

class Solution {
    public long maxSubarraySum(int[] nums, int k) {
        int n = nums.length;
        HashMap<Long, Long> map = new HashMap<>();
        long pre = 0, maxi = Long.MIN_VALUE;
        for (int j = 0; j < n; j++) {
            long current = j % k;
            if (!map.containsKey(current)) map.put(current, pre);
            else map.put(current, Math.min(map.get(current), pre));
            pre += nums[j];
            long to_check = ((j % k) + (1 % k) + k) % k;
            if (map.containsKey(to_check)) maxi = Math.max(maxi, pre - map.get(to_check));
        }
        return maxi;
    }
}

Complexity Analysis¶

Time Complexity: O(?)
Space Complexity: O(?)

Approach¶

Detailed explanation of the approach will be added here