Maximum sum of a subarray

Array, Sliding Window

Finds the maximum sum of a subarray of size k in an array.

Solutions

Approach - Brute Force Technique

Steps

1. Initialize Variables: The algorithm starts by initializing a variable maxSum to int.MinValue. This will keep track of the maximum sum found so far.

2. Iterate Over Array: The algorithm then enters a nested loop that iterates over each possible subarray of size k in nums.

   • Calculate Subarray Sum: For each subarray, the algorithm calculates the sum of the elements in the subarray.

   • Update Max Sum: The algorithm updates maxSum to be the maximum of maxSum and the sum of the current subarray.

3. Return Result: After the loops, the algorithm returns maxSum, which is the maximum sum of a subarray of size k.

public class Solution {
    public int MaxSum(int[] nums, int k) {
        int maxSum = int.MinValue;
        for (int start = 0; start <= nums.Length - k; start++) {
            int sum = 0;
            for (int i = start; i < start + k; i++) {
                sum += nums[i];
            }
            maxSum = Math.Max(maxSum, sum);
        }
        return maxSum;
    }
}

Complexity

• Time complexity: O(N*K)

• Space complexity: O(1)

The time complexity of this algorithm is O(n*k), where n is the length of the input array nums. This is because the algorithm uses a nested loop to iterate over each possible subarray of size k in nums.

The space complexity of this algorithm is O(1), which means the space required by the algorithm does not increase with the size of the input array. This is because the algorithm only uses a fixed amount of space to store the variables start, i, sum, and maxSum.

Approach -Sliding Window

In this technique, a window of a specific size is moved over the array. The window size in your case is k. The window is first placed at the beginning of the array and then it “slides” over the array by one position at a time

Steps

1. Check Array Length: The algorithm starts by checking if the length of the array arr is less than k. If it is, the algorithm returns -1 because it’s not possible to find a subarray of size k.

2. Calculate Initial Sum: The algorithm then calculates the sum of the first k elements in arr and stores it in max_sum.

3. Initialize Window Sum: The algorithm initializes window_sum to max_sum. This variable will keep track of the sum of the current window of size k.

4. Iterate Over Array: The algorithm then enters a loop that iterates over the rest of the elements in arr.

   • Update Window Sum: For each element, the algorithm adds the element’s value to window_sum and subtracts the value of the element that is now outside the window.

   • Update Max Sum: The algorithm updates max_sum to be the maximum of max_sum and window_sum.

5. Return Result: After the loop, the algorithm returns max_sum, which is the maximum sum of a subarray of size k.

public class Program
{
     
     int MaxSum(int[] arr, int k)
    {
        int n = arr.Length;
        if (n < k)
        {
            return -1;
        }

        int max_sum = 0;
        for (int i = 0; i < k; i++)
            max_sum += arr[i];

        int window_sum = max_sum;
        for (int i = k; i < n; i++)
        {
            window_sum += arr[i] - arr[i - k];
            max_sum = Math.Max(max_sum, window_sum);
        }

        return max_sum;
    }
}

Complexity

• Time complexity: O(N)

• Space complexity: O(1)

The time complexity of this algorithm is O(n), where n is the length of the input array arr. This is because the algorithm processes each element exactly once.

The space complexity of this algorithm is O(1), which means the space required by the algorithm does not increase with the size of the input array. This is because the algorithm only uses a fixed amount of space to store the variables n, k, max_sum, window_sum, and i.