Maximum Length Subarray - C++ Solution

1. Introduction

The "Maximum Length Subarray" problem is a classic in algorithmic challenges, focusing on array manipulation and efficient use of data structures. The goal is to find a contiguous subarray within an integer array that sums up to a given target and has the maximum possible length. This problem tests the ability to implement efficient searching and hashing techniques.

Problem

Given an array of integers, the task is to find a contiguous subarray that adds up to a specified target sum and has the maximum length among all such subarrays. The solution should return any one of these maximum-length subarrays.

2. Solution Steps

1. Use a hash map to store the cumulative sum and its first occurrence index.

2. Traverse the array, maintaining the cumulative sum of elements.

3. For each sum, check if the sum minus the target exists in the hash map.

4. If it does, calculate the length of the current subarray and update the maximum length if necessary.

5. If the cumulative sum is new, add it to the hash map with its index.

6. Continue this process until the end of the array.

7. Extract the subarray of maximum length that sums up to the target.

3. Code Program

#include <iostream>
#include <unordered_map>
#include <vector>
using namespace std;

// Function to find the maximum length subarray with a given sum
vector<int> maxLenSubarray(vector<int>& nums, int target) {
    unordered_map<int, int> sumMap; // Map to store cumulative sum and its index
    int sum = 0, maxLength = 0, endIndex = -1; // Initialize variables

    for (int i = 0; i < nums.size(); i++) {
        sum += nums[i]; // Update cumulative sum

        // If the subarray starts from index 0
        if (sum == target) {
            maxLength = i + 1;
            endIndex = i;
        }

        // Make an entry for sum if it is not present in sumMap
        if (sumMap.find(sum) == sumMap.end()) {
            sumMap[sum] = i;
        }

        // Check if there exists a subarray with target sum
        if (sumMap.find(sum - target) != sumMap.end()) {
            if (maxLength < i - sumMap[sum - target]) {
                maxLength = i - sumMap[sum - target];
                endIndex = i;
            }
        }
    }

    // Return the maximum length subarray
    if (endIndex != -1) {
        return vector<int>(nums.begin() + (endIndex - maxLength + 1), nums.begin() + endIndex + 1);
    } else {
        return {};
    }
}

int main() {
    vector<int> nums = {5, 6, -5, 5, 3, 5, 3, -2, 0}; // Test array
    int target = 8;
    vector<int> result = maxLenSubarray(nums, target); // Find maximum length subarray

    // Print the result
    for (int num : result) {
        cout << num << " ";
    }
    cout << endl;

    return 0;
}

Output:

-5 5 3 5

Explanation:

The function maxLenSubarray uses a hash map to efficiently track the cumulative sums and their first occurrences. 

It traverses the array, updating the sum, and checks if a subarray with the desired sum exists. If such a subarray is found and its length is greater than the current maximum, the maximum length and the end index of the subarray are updated. 

This approach ensures that the longest subarray with the target sum is found, making the solution efficient for arrays of varying sizes.