...

/

Solution: Maximum Sum Subarray of Size k

Solution: Maximum Sum Subarray of Size k

Review various solution approaches to the Maximum Sum Subarray of Size k problem in detail.

Solution 1

A naive solution to this problem is to find the sum of all possible contiguous subarrays of size kk, find the maximum of those sums, and return that sum. This approach can easily be implemented using two for loops.

using System;
class Program
{
/// <summary>
/// Finds the maximum sum of a sub-array with a given window size.
/// </summary>
/// <param name="arr">Array of integers.</param>
/// <param name="k">Window size of the sub-array.</param>
/// <returns>The maximum sum of a sub-array with the specified window size.</returns>
public static int MaxSubArrayOfSizeK(int[] arr, int k)
{
int maxSum = 0;
int windowSum = 0;
// Iterate through the array with a sliding window of size k
for (int i = 0; i <= arr.Length - k; i++)
{
windowSum = 0;
// Sum the elements in the current window
for (int j = i; j < i + k; j++)
{
windowSum += arr[j];
}
// Update the maximum sum
maxSum = Math.Max(maxSum, windowSum);
}
return maxSum;
}
// Driver code to test above method
public static void Main()
{
// Test cases
int[] array1 = { 2, 1, 5, 1, 3, 2 };
int k1 = 3;
Console.WriteLine("Maximum sum of a sub-array of size K: " + MaxSubArrayOfSizeK(array1, k1));
int[] array2 = { 2, 3, 4, 1, 5 };
int k2 = 2;
Console.WriteLine("Maximum sum of a sub-array of size K: " + MaxSubArrayOfSizeK(array2, k2));
}
}

Explanation

  • Line 17: The outer for loop runs for the ArraySizek+1ArraySize - k + 1 ...