[BUG] - Maximum Subarray Sum With Length Divisible by K #33729
Description
LeetCode Username
Pixelrick420
Problem Number, Title, and Link
- Maximum Subarray Sum With Length Divisible by K https://leetcode.com/problems/maximum-subarray-sum-with-length-divisible-by-k/
Bug Category
Problem description
Bug Description
The problem description says:
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.
A number n is considered to be divisible by another number k if dividing n by k yields remainder 0.
By the above definition, the number 0 is divisible by any natural number n.
Thus, the empty subarray [] with length 0 is a valid subarray of nums such that size of the subarray divisible by k. The sum of elements in the empty subarray [] is 0 by convention.
Now consider the following test case:
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.
The output of the test case based on the description, should be 0 as [] is the subarray with maximum sum such that the size of the subarray is divisible by k.
Language Used for Code
Python/Python3
Code used for Submit/Run operation
class Solution:
def maxSubarraySum(self, nums: List[int], k: int) -> int:
n = len(nums)
remToPref = [[] for _ in range(k)]
remToPref[0].append(0)
out = 0
curSum = 0
for i in range(n):
curSum += nums[i]
remToPref[(i + 1) % k].append(curSum)
for i in range(k):
m = len(remToPref[i])
if m < 2:
continue
curMin = nums[0]
for j in range(1, m):
out = max(out, remToPref[i][j] - curMin)
curMin = min(curMin, remToPref[i][j])
return outExpected behavior
As the current problem description does not rule out subarrays of length 0, the output 0 should be accepted as the correct answer.
Instead, the expected answer is -10 which is the maximum sum of elements of the subarray with non zero length that meets the requirements.
This could be fixed in 2 ways:
- Add a line to the description that explicitly states that the subarray length should be non zero.
or - Accept
0as the correct answer in this situation.
Screenshots
Additional context
No response