In many array or linked list problems, we are often required to find or compute a specific value across all contiguous subarrays (or sublists) of a given size.

A classic example of this is the Sliding Window Maximum problem, where we need to determine the maximum value in every subarray of size k.

Input : arr[] = {100, 200, 300, 400}, k = 2 

Output: 700

Let’s first understand the problem. As a good practice, we should always begin by designing a brute-force approach to clear up the logic and then work on optimizing that solution for better performance.

Brute Force Approach :

Initialize ans = arr[0]

for i from 0 to n - k:
    cur = 0
    for j from i to i + k - 1:
        cur += arr[j]
    if cur > ans:
        ans = cur

return ans

🧠 Logic Behind the Pseudocode :

We start by setting ans (our result variable) to the first element of the array, just to have a baseline for comparison.

Initialize ans = arr[0] = 100

We’re looping through all starting indices of possible subarrays of size k.

• n = 4 (length of array),

• So we go from i = 0 to i = 2 (because i + k - 1 must stay within array bounds)

    for i from 0 to n - k:
  

  For each starting index i, we calculate the sum of the subarray of size k starting from i.
  We use a nested loop to sum the next k elements starting at i, storing the result in cur

        cur = 0
        for j from i to i + k - 1:
            cur += arr[j]
  

  If the current sum cur is greater than our previously stored maximum sum ans, we update ans.

  
    return ans
  

  Dry Run :

  
    i = 0: subarray = [100, 200], sum = 300 → ans = max(100, 300) = 300
  
    i = 1: subarray = [200, 300], sum = 500 → ans = max(300, 500) = 500
  
    i = 2: subarray = [300, 400], sum = 700 → ans = max(500, 700) = 700
  

  Time complexity :

  The outer loop runs (n — k + 1) times.

  The inner loop runs k times.

  So total operations = (n — k + 1) k ➡️ Time Complexity = O((n — k + 1) k) = O(n * k) in the worst case.

---

Can we find a better solution?

An efficient approach is to treat each contiguous subarray as a sliding window. For example, with a window of 5 elements, instead of recalculating the sum for every new subarray, we update the previous sum by subtracting the element that exits the window and adding the new element that enters. This reuse of the previous computation reduces redundant operations and lowers the time complexity to O(N).

---

1st window

[ 100, 200, 300, 400 ]
   └─────┘
   Window

2nd window

[ 100, 200, 300, 400 ]
       └─────┘
        Window

3rd window

[ 100, 200, 300, 400 ]

            └─────┘

            Window

Code

public int maximumSum(int[] arr, int k) {
       int maxSum = 0;
       int windowSum = 0;
       int slide = 0;
       for (int i = 0; i < arr.length; i++) {
           windowSum += arr[i];
           if (i >= k - 1) {
              maxSum = Math.max(maxSum, windowSum);
              windowSum -= arr[slide];
              slide++;
              }
        }
       return maxSum;
}

Time Complexity : O(n)

Space Complexity : O(1)