Py3 C C++ prefix sum解Leetcode 3381 Maximum Subarray Sum With Length Div...

Py3 C C++ prefix sum解Leetcode 3381  Maximum Subarray Sum With Length Divisible by K

Very similar to Kadane's algorithm

[Py3 code請進]

[codes on Leetcode]https://leetcode.com/problems/maximum-subarray-sum-with-length-divisible-by-k/solutions/7376601/prefix-sum-record-min-sum-mod-kbeats-100-qmld/

class Solution:
    def maxSubarraySum(self, nums: List[int], k: int) -> int:
        n=len(nums)
        minS=[inf]*(k-1)+[0]
        prefix, ans=0, -inf
        for i, x in enumerate(nums):
            prefix+=x
            ik=i%k
            ans=max(ans, prefix-minS[ik])
            minS[ik]=min(prefix, minS[ik])
        return ans