Skip to content

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

Solutions

Solution 1: Prefix Sum + Enumeration

According to the problem description, for a subarray's length to be divisible by \(k\), it is equivalent to requiring that for subarray \(\textit{nums}[i+1 \ldots j]\), we have \(i \bmod k = j \bmod k\).

We can enumerate the right endpoint \(j\) of the subarray and use an array \(\textit{f}\) of length \(k\) to record the minimum prefix sum for each modulo \(k\). Initially, \(\textit{f}[k-1] = 0\), indicating that the prefix sum at index \(-1\) is \(0\).

Then for the current right endpoint \(j\) with prefix sum \(s\), we can calculate the maximum sum of subarrays ending at \(j\) with length divisible by \(k\) as \(s - \textit{f}[j \bmod k]\), and update the answer accordingly. At the same time, we need to update \(\textit{f}[j \bmod k]\) to be the minimum of the current prefix sum \(s\) and \(\textit{f}[j \bmod k]\).

After the enumeration is complete, return the answer.

The time complexity is \(O(n)\) and the space complexity is \(O(k)\), where \(n\) is the length of the array \(\textit{nums}\).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
class Solution:
    def maxSubarraySum(self, nums: List[int], k: int) -> int:
        f = [inf] * k
        ans = -inf
        s = f[-1] = 0
        for i, x in enumerate(nums):
            s += x
            ans = max(ans, s - f[i % k])
            f[i % k] = min(f[i % k], s)
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
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;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution {
public:
    long long maxSubarraySum(vector<int>& nums, int k) {
        using ll = long long;
        ll inf = 1e18;
        vector<ll> f(k, inf);
        ll ans = -inf;
        ll s = 0;
        f[k - 1] = 0;
        for (int i = 0; i < nums.size(); ++i) {
            s += nums[i];
            ans = max(ans, s - f[i % k]);
            f[i % k] = min(f[i % k], s);
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
func maxSubarraySum(nums []int, k int) int64 {
    inf := int64(1) << 62
    f := make([]int64, k)
    for i := range f {
        f[i] = inf
    }
    f[k-1] = 0

    var s, ans int64
    ans = -inf
    for i := 0; i < len(nums); i++ {
        s += int64(nums[i])
        ans = max(ans, s-f[i%k])
        f[i%k] = min(f[i%k], s)
    }

    return ans
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
function maxSubarraySum(nums: number[], k: number): number {
    const f: number[] = Array(k).fill(Infinity);
    f[k - 1] = 0;
    let ans = -Infinity;
    let s = 0;
    for (let 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;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
impl Solution {
    pub fn max_subarray_sum(nums: Vec<i32>, k: i32) -> i64 {
        let k = k as usize;
        let inf = 1i64 << 62;
        let mut f = vec![inf; k];
        f[k - 1] = 0;
        let mut s = 0i64;
        let mut ans = -inf;
        for (i, &x) in nums.iter().enumerate() {
            s += x as i64;
            ans = ans.max(s - f[i % k]);
            f[i % k] = f[i % k].min(s);
        }
        ans
    }
}

Comments