Repository: TheAlgorithms/Java
Pull request #6001 (2024-10-25 15:20:32)

Add Sliding Window algorithm and tests for maximum sum of subarray
<!--
Thank you for your contribution!
In order to reduce the number of notifications sent to the maintainers, please:
- create your PR as draft, cf. https://docs.github.com/en/pull-requests/collaborating-with-pull-requests/proposing-changes-to-your-work-with-pull-requests/about-pull-requests#draft-pull-requests,
- make sure that all of the CI checks pass,
- mark your PR as ready for review, cf. https://docs.github.com/en/pull-requests/collaborating-with-pull-requests/proposing-changes-to-your-work-with-pull-requests/changing-the-stage-of-a-pull-request#marking-a-pull-request-as-ready-for-review
-->

<!-- For completed items, change [ ] to [x] -->

- [x] I have read [CONTRIBUTING.md](https://github.com/TheAlgorithms/Java/blob/master/CONTRIBUTING.md).
- [x] This pull request is all my own work -- I have not plagiarized it.
- [x] All filenames are in PascalCase.
- [x] All functions and variable names follow Java naming conventions.
- [x] All new algorithms have a URL in their comments that points to Wikipedia or other similar explanations.
- [x] All new code is formatted with `clang-format -i --style=file path/to/your/file.java`

Chiefpatwal: This pull request introduces a new module for the Sliding Window technique, including both the main implementation and the corresponding unit tests. The primary feature added is the MaxSumKSizeSubarray algorithm, which efficiently calculates the maximum sum of a subarray of a fixed size kk within a given array. The implementation follows best practices and includes comprehensive tests to ensure correctness and performance. I look forward to your feedback and suggestions for further improvements.

Patch:
diff --git a/src/main/java/com/thealgorithms/slidingwindow/MaxSumKSizeSubarray.java b/src/main/java/com/thealgorithms/slidingwindow/MaxSumKSizeSubarray.java
new file mode 100644
index 00000000..7e8095e0
--- /dev/null
+++ b/src/main/java/com/thealgorithms/slidingwindow/MaxSumKSizeSubarray.java
@@ -0,0 +1,50 @@
+package com.thealgorithms.slidingwindow;
+
+/**
+ * The Sliding Window algorithm is used to find the maximum sum of a subarray
+ * of a fixed size k within a given array.
+ *
+ * <p>
+ * Worst-case performance O(n)
+ * Best-case performance O(n)
+ * Average performance O(n)
+ * Worst-case space complexity O(1)
+ *
+ * @author Your Name (https://github.com/Chiefpatwal)
+ */
+public final class MaxSumKSizeSubarray {
+
+    // Prevent instantiation
+    private MaxSumKSizeSubarray() {
+    }
+
+    /**
+     * This method finds the maximum sum of a subarray of a given size k.
+     *
+     * @param arr is the input array where the maximum sum needs to be found
+     * @param k   is the size of the subarray
+     * @return the maximum sum of the subarray of size k
+     */
+    public static int maxSumKSizeSubarray(int[] arr, int k) {
+        if (arr.length < k) {
+            return -1; // Edge case: not enough elements
+        }
+
+        int maxSum;
+        int windowSum = 0;
+
+        // Calculate the sum of the first window
+        for (int i = 0; i < k; i++) {
+            windowSum += arr[i];
+        }
+        maxSum = windowSum;
+
+        // Slide the window across the array
+        for (int i = k; i < arr.length; i++) {
+            windowSum += arr[i] - arr[i - k];
+            maxSum = Math.max(maxSum, windowSum);
+        }
+
+        return maxSum;
+    }
+}


Test patch:
diff --git a/src/test/java/com/thealgorithms/slidingwindow/MaxSumKSizeSubarrayTest.java b/src/test/java/com/thealgorithms/slidingwindow/MaxSumKSizeSubarrayTest.java
new file mode 100644
index 00000000..aa3c2eae
--- /dev/null
+++ b/src/test/java/com/thealgorithms/slidingwindow/MaxSumKSizeSubarrayTest.java
@@ -0,0 +1,79 @@
+package com.thealgorithms.slidingwindow;
+
+import static org.junit.jupiter.api.Assertions.assertEquals;
+
+import org.junit.jupiter.api.Test;
+
+/**
+ * Unit tests for the MaxSumKSizeSubarray class.
+ *
+ * @author Your Name (https://github.com/Chiefpatwal)
+ */
+class MaxSumKSizeSubarrayTest {
+
+    /**
+     * Test for the basic case of finding the maximum sum.
+     */
+    @Test
+    void testMaxSumKSizeSubarray() {
+        int[] arr = {1, 2, 3, 4, 5};
+        int k = 2;
+        int expectedMaxSum = 9; // 4 + 5
+        assertEquals(expectedMaxSum, MaxSumKSizeSubarray.maxSumKSizeSubarray(arr, k));
+    }
+
+    /**
+     * Test for a different array and subarray size.
+     */
+    @Test
+    void testMaxSumKSizeSubarrayWithDifferentValues() {
+        int[] arr = {2, 1, 5, 1, 3, 2};
+        int k = 3;
+        int expectedMaxSum = 9; // 5 + 1 + 3
+        assertEquals(expectedMaxSum, MaxSumKSizeSubarray.maxSumKSizeSubarray(arr, k));
+    }
+
+    /**
+     * Test for edge case with insufficient elements.
+     */
+    @Test
+    void testMaxSumKSizeSubarrayWithInsufficientElements() {
+        int[] arr = {1, 2};
+        int k = 3; // Not enough elements
+        int expectedMaxSum = -1; // Edge case
+        assertEquals(expectedMaxSum, MaxSumKSizeSubarray.maxSumKSizeSubarray(arr, k));
+    }
+
+    /**
+     * Test for large array.
+     */
+    @Test
+    void testMaxSumKSizeSubarrayWithLargeArray() {
+        int[] arr = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
+        int k = 5;
+        int expectedMaxSum = 40; // 6 + 7 + 8 + 9 + 10
+        assertEquals(expectedMaxSum, MaxSumKSizeSubarray.maxSumKSizeSubarray(arr, k));
+    }
+
+    /**
+     * Test for array with negative numbers.
+     */
+    @Test
+    void testMaxSumKSizeSubarrayWithNegativeNumbers() {
+        int[] arr = {-1, -2, -3, -4, -5};
+        int k = 2;
+        int expectedMaxSum = -3; // -1 + -2
+        assertEquals(expectedMaxSum, MaxSumKSizeSubarray.maxSumKSizeSubarray(arr, k));
+    }
+
+    /**
+     * Test for the case where k equals the array length.
+     */
+    @Test
+    void testMaxSumKSizeSubarrayWithKEqualToArrayLength() {
+        int[] arr = {1, 2, 3, 4, 5};
+        int k = 5;
+        int expectedMaxSum = 15; // 1 + 2 + 3 + 4 + 5
+        assertEquals(expectedMaxSum, MaxSumKSizeSubarray.maxSumKSizeSubarray(arr, k));
+    }
+}