3381. Maximum Subarray Sum With Length Divisible by K
Approach
Prefix sums mod k tracking; for each prefix[i] add current prefix minus min prefix of same mod.
Key Techniques
Array problems involve manipulating elements stored in a contiguous block of memory. Key techniques include two-pointer traversal, prefix sums, sliding windows, and in-place partitioning. In C#, arrays are zero-indexed and fixed in size — use List<T> when you need dynamic resizing.
The sliding window technique maintains a dynamic sub-array (or substring) of interest, expanding the right boundary and shrinking the left boundary based on a constraint. It reduces O(n²) substring enumeration to O(n). Track state (frequency map, sum, distinct count) incrementally.
A prefix sum array pre-computes cumulative values so any range query is answered in O(1). The classic sum of range [l, r] = prefix[r+1] - prefix[l]. 2D prefix sums extend this to matrix sub-rectangle queries. Combine with a hash map for "subarray sum equals k" problems.
// Approach: Prefix sums mod k tracking; for each prefix[i] add current prefix minus min prefix of same mod.
// Time: O(n) Space: O(k)
public class Solution
{
public long MaxSubarraySum(int[] nums, int k)
{
long ans = long.MinValue;
long prefix = 0;
long[] minPrefix = new long[k];
for (int i = 0; i < k; i++)
minPrefix[i] = long.MaxValue / 2;
minPrefix[k - 1] = 0;
for (int i = 0; i < nums.Length; ++i)
{
prefix += nums[i];
ans = Math.Max(ans, prefix - minPrefix[i % k]);
minPrefix[i % k] = Math.Min(minPrefix[i % k], prefix);
}
return ans;
}
}