Solution: Maximum Sum Subarray of Size k
Review various solution approaches to the Maximum Sum Subarray of Size k problem in detail.
We'll cover the following...
Solution 1
A naive solution to this problem is to find the sum of all possible contiguous subarrays of size , 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 kfor (int i = 0; i <= arr.Length - k; i++){windowSum = 0;// Sum the elements in the current windowfor (int j = i; j < i + k; j++){windowSum += arr[j];}// Update the maximum summaxSum = Math.Max(maxSum, windowSum);}return maxSum;}// Driver code to test above methodpublic static void Main(){// Test casesint[] 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 ...