Start learning free

LESSON 211 OF 347 · PARTIAL SUMS #1

Maximum Sum Subarray of Length K in C#: Brute Force

Practice O(n * k) 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. Among all contiguous subarrays of length exactly k, it must find the one with the largest sum, and return its first and last index as a two-element int[].

    In the example, nums = [5, 6, 1, 2, 6, 6, 4, 3] and k = 3. The window from index 4 to index 6 holds 6, 6, 4, which sums to 16, more than any other window of three. The method returns [4, 6]. If two windows tie, the lesson's steps keep the earlier one.

    Approach: add up every window

    An array of length n has n - k + 1 windows of length k: one for each start index from 0 up to n - k. The brute force computes each window's sum from scratch with an inner loop, and remembers the best one along with its bounds.

    This costs k additions for each of the n - k + 1 windows, so the time is O(n * k). The next lesson on this problem slides the window instead: it subtracts the element that leaves and adds the one that enters, which brings the time to O(n). Start here, since the brute force shows exactly what the sliding window saves.

    Here are the windows for the example, with their sums:

    start 0: [5, 6, 1] = 12
start 1: [6, 1, 2] = 9
start 2: [1, 2, 6] = 9
start 3: [2, 6, 6] = 14
start 4: [6, 6, 4] = 16
start 5: [6, 4, 3] = 13

    Eight elements and k = 3 give six windows, which is 8 - 3 + 1. The largest sum is 16, at start 4, so the window runs from index 4 to index 6. This is the table the two loops build one row at a time, keeping only the best row.

    Step by step

    1. Track the best sum. maxSum starts at int.MinValue, so the first window always beats it. Starting at 0 would fail when every window has a negative sum.
    2. Prepare the answer. answer starts as an empty array. It is never filled in place: each time a better window appears, the variable is pointed at a new two-element array.
    3. Loop over window starts. The index i goes from 0 to nums.Length - k inclusive. The condition is <= because the last window starts at nums.Length - k itself, and ends at the final element.
    4. Sum one window. Inside the loop, sum starts at 0 for every window. An inner loop with idx from i up to but not including i + k visits exactly k positions and adds each nums[idx].
    5. Compare. If sum > maxSum, store the new best sum and the window's bounds, i and i + k - 1. The strict > means a later window with an equal sum doesn't replace an earlier one.
    6. Return. After the loops, answer holds the bounds of the best window.

    The solution in C#

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

    C# details worth noticing

    • Arrays have a fixed length. You can't append to answer, so the code creates a new array with new int[]{i, i + k - 1} and replaces the old one. The new int[]{} at the start is a valid array with zero elements.
    • Printing an array. Console.WriteLine(answer) prints the type name, not the contents. To see 4, 6, use string.Join(", ", answer).
    • Integer overflow. Sums of int values wrap around silently when they exceed 2,147,483,647. With very large numbers, a long sum would be needed; the lesson's inputs fit comfortably in an int.

    Complexity

    Time: O(n * k). There are n - k + 1 windows and each costs k additions. When k is small this is fast, but when k is about n / 2 it grows like n².

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

    Look at the table again: neighbouring windows share most of their elements. The window at start 1 is the window at start 0 without the 5 and with an extra 2. The brute force ignores this overlap and re-adds the shared elements each time, which is exactly the waste that the sliding window removes.

    Edge cases and common mistakes

    • Off-by-one in the outer bound. Writing i < nums.Length - k skips the last window. For [1, 2, 3] with k = 2 it would only try the window [1, 2] and miss the best one, [2, 3].
    • Resetting sum in the wrong place. Declaring sum before the outer loop makes each window start from the previous window's total. It belongs inside the outer loop, so every window starts at 0.
    • Window end. The window starting at i ends at i + k - 1, not i + k.
    • All negative numbers. For [-3, -1, -2] and k = 1, the answer is [1, 1]. The int.MinValue start handles this.
    • Ties. For [2, 1, 1, 2] and k = 2, the windows at indices 0 and 2 both sum to 3. The strict comparison keeps the earlier one, so the answer is [0, 1]. Using >= would return [2, 3] instead.
    • k larger than the array. The outer loop never runs and the method returns the empty array. The lesson's inputs don't test this, but you should know what happens.

    Testing

    • [5, 6, 1, 2, 6, 6, 4, 3] with k = 3 returns [4, 6].
    • [-3, -1, -2] with k = 1 returns [1, 1].
    • [2, 1, 1, 2] with k = 2 returns [0, 1].
    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