2025-11-27 Daily Challenge

Posted on:
Posted modified:
In: DailyChallenge

Today I have done leetcode's November LeetCoding Challenge with cpp.

November LeetCoding Challenge 27

Description

Maximum Subarray Sum With Length Divisible by K

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

Solution

class Solution {
public:
  long long maxSubarraySum(vector<int>& nums, int k) {
    int len = nums.size();
    if(k == len) {
      long long answer = 0;
      for(auto n : nums) answer += n;
      return answer;
    }
    vector<long long> sums(k + 1);
    long long sum = 0;
    long long answer = LONG_LONG_MIN;
    for(int i = 0; i < len; ++i) {
      sum += nums[i];
      if(i >= k - 1) {
        answer = max(answer, sum - sums[(i + 1) % k]);
        sums[(i + 1) % k] = min(sum, sums[(i + 1) % k]);
      } else {
        sums[i + 1] = sum;
      }
    }
    return answer;
  }
};

// Accepted
// 661/661 cases passed (8 ms)
// Your runtime beats 76.85 % of cpp submissions
// Your memory usage beats 99.33 % of cpp submissions (160.6 MB)
Algorithm