Start learning free

LESSON 212 OF 347 · PARTIAL SUMS #1

Maximum Sum Subarray of Length K in C#: O(n) Sliding Window

Practice O(n) Read the full explanation

Given an input array of integers and a positive integer k, find out the maximum sum of a contiguous subarray of length exactly k

Example

Input: nums = [5, 6, 1, 2, 6, 6, 4, 3], k = 3
Output: 4 6
Explanation: The subarray nums[4...6] has the maximum sum of 16
STEP 1 OF 8
    Ctrl + Enter to check

    C# · PARTIAL SUMS #1

    Maximum Sum Subarray Of Length K in C#, explained

    Problem overview

    The method MaxSum receives an int[] nums and a positive int k. It must find the contiguous subarray of length exactly k with the largest sum, and return its first and last index as an int[].

    For nums = [5, 6, 1, 2, 6, 6, 4, 3] and k = 3, the best window is [6, 6, 4], which sums to 16 and sits at indices 4 to 6. The method returns [4, 6]. When two windows have the same sum, the lesson's steps return the earlier one.

    Approach: slide the window instead of re-adding it

    The brute-force lesson on this problem adds up k elements for every window, which costs O(n * k). But two neighbouring windows share k - 1 elements. Moving the window one step to the right changes exactly two things: the leftmost element leaves, and a new element enters on the right. So the new sum is the old sum, minus the element that left, plus the element that entered. That is two operations per window, whatever k is.

    The plan is to compute the first window's sum the slow way, once, and then slide across the rest of the array updating the sum in constant time. The total work is one pass over the array, which is O(n).

    Step by step

    1. Start the answer at the first window. answer is {0, k - 1}. If no later window has a bigger sum, the first one is the answer, so it is the right default. Starting with an empty array would return nothing whenever the first window is the best.
    2. Add up the first window. A loop over the indices 0 to k - 1 accumulates sum.
    3. Record it as the best so far. maxSum is initialised from sum.
    4. Slide. A second loop runs i from 1 to nums.Length - k inclusive, where i is the start of the current window. The condition uses <= because the last window begins at nums.Length - k.
    5. Update the sum. The previous window started at i - 1, so nums[i - 1] has just left. The current window ends at i + k - 1, so nums[i + k - 1] has just entered.
    6. Compare. If the new sum is strictly greater than maxSum, update both maxSum and answer. The strict comparison keeps the earlier window on a tie.
    7. Return answer.

    Traced on the example, the sums are 12 for the first window, then 12 - 5 + 2 = 9, then 9 - 6 + 6 = 9, then 9 - 1 + 6 = 14, then 14 - 2 + 4 = 16, then 16 - 6 + 3 = 13. The best is 16, found when i = 4, so answer ends up as {4, 6}.

    The solution in C#

    class Solution {
    public int[] MaxSum(int[] nums, int k) {
        int[] answer = new int[]{0, k - 1};
        int sum = 0;
        for (int i = 0; i < k; i++) {
            sum += nums[i];
        }
        int maxSum = sum;
        for (int i = 1; i <= nums.Length - k; i++) {
            sum = sum - nums[i - 1] + nums[i + k - 1];
            if (sum > maxSum) {
                maxSum = sum;
                answer = new int[]{i, i + k - 1};
            }
        }
        return answer;
    }
}

    C# details worth noticing

    • Two loops, two scopes. Both loops declare their own int i. That is allowed because each i exists only inside its own for statement. Declaring i twice in the same scope would not compile.
    • Array initialisers. new int[]{0, k - 1} creates a two-element array whose values can be any expressions, not just constants. Arrays can't grow, so each improvement creates a fresh array.
    • Overflow. If the array held values near the int limits, the running sum could wrap around without any error. The lesson's data stays small.

    Why the update is safe

    The update works because the window sum is always the sum of exactly the elements currently inside the window. Before the update it covers indices i - 1 to i + k - 2. Removing the first and adding the one after the last leaves indices i to i + k - 1, which is the new window. Nothing else changes, so no element is ever counted twice or missed.

    Complexity

    Time: O(n). The first loop does k additions and the second does n - k iterations of constant work, so about n steps in total, regardless of k.

    Space: O(1) beyond the two-element result.

    Edge cases and common mistakes

    • Using the wrong element for entering or leaving. Subtracting nums[i] or adding nums[i + k] is a common off-by-one. Check with i = 1: the window is indices 1 to k, so the leaving element is index 0 and the entering one is index k, which is i + k - 1.
    • k equal to the array length. There is exactly one window. The second loop starts at 1 and the condition 1 <= 0 is false, so the method returns {0, k - 1}.
    • k larger than the array. The first loop reads past the end of nums and throws an IndexOutOfRangeException. The lesson's inputs always have k within the length, but code that accepts arbitrary input should check first.
    • All negative numbers. Initialising maxSum from the first window, rather than 0, makes this work. For [-3, -1, -2] with k = 2, the sums are -4 and -3, so the answer is [1, 2].
    • Ties. The strict > keeps the earlier window: [2, 1, 1, 2] with k = 2 returns [0, 1].

    Key takeaways

    • When consecutive subarrays overlap almost completely, update the sum instead of recomputing it.
    • Seed the best value from the first real candidate, not from 0.
    • The loop's last start index is nums.Length - k, which needs <=.
    Keep going with C#About 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free