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] <= 109According 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}$.
Java
C++
Go
TypeScript
Rust
Practice Maximum Subarray Sum With Length Divisible by K with our built-in code editor and test cases.
Practice on FleetCode