1. Introduction

Finding the maximum length subarray with a given sum is a common problem that comes up in array-based algorithms. This problem can be tackled using multiple approaches, including a brute-force method or using hashing for a more optimal solution. In this blog, we will solve the problem using a hashing approach.

2. Program Steps

1. Create a hashmap to store the end-index of all subarrays having a given sum.

2. Maintain the sum of elements in a variable while iterating the array.

3. For each sum encountered, check if it is equal to the given sum.

4. Also, check if sum – given sum exists in the map or not.

5. Update the maximum length and ending index for each valid subarray.

6. Return the maximum length subarray with the given sum.

3. Code Program

public class MaxLengthSubarray {

    public static int maxLengthSubarray(int[] arr, int sum) {
        // Create a hashmap to store end index of all subarrays having given sum
        java.util.Map<Integer, Integer> map = new java.util.HashMap<>();

        // Insert (0, -1) pair into the map to handle the case when subarray with sum starts from index 0
        map.put(0, -1);

        int sum_so_far = 0;
        int len = 0;
        int ending_index = -1;

        for (int i = 0; i < arr.length; i++) {
            // Sum of elements so far in the array
            sum_so_far += arr[i];

            // If sum is seen for the first time, insert sum with its index into the map
            if (!map.containsKey(sum_so_far)) {
                map.put(sum_so_far, i);
            }

            // Update length and ending index of maximum length subarray having a given sum
            if (map.containsKey(sum_so_far - sum) && len < i - map.get(sum_so_far - sum)) {
                len = i - map.get(sum_so_far - sum);
                ending_index = i;
            }
        }

        // Print the subarray
        if (ending_index != -1) {
            System.out.println("Subarray found from Index " + (ending_index - len + 1) + " to " + ending_index);
        } else {
            System.out.println("No subarray exists");
        }

        return len;
    }

    public static void main(String[] args) {
        int[] arr = {5, 6, -5, 5, 3, 5, 3, -2, 0};
        int sum = 8;
        System.out.println("The maximum length subarray has length: " + maxLengthSubarray(arr, sum));
    }
}

Output:

Subarray found from Index 2 to 4
The maximum length subarray has length: 3

4. Step By Step Explanation

1. We start by initializing an empty map that will be used to store the end index of all subarrays with the given sum.

2. As we traverse the array, we keep a running sum of elements.

3. If the sum encountered minus the given sum exists in the map, it indicates the presence of a subarray with the desired sum.

4. Using the stored index from the map, we update our maximum length and ending index if a larger subarray with the given sum is found.

5. By the end of the loop, we either find the maximum length subarray with the given sum or determine that no such subarray exists.