Posted on by Kalkicode
Code Array

# Find max length subarray with given sum

The problem involves finding the maximum length subarray within a given array of integers that adds up to a specific target sum. This problem is a classic example of a sliding window technique used to efficiently solve subarray-related problems.

## Problem Statement

Given an array of integers and a target sum, find the maximum length of a subarray such that the sum of its elements equals the given target sum.

## Example

Consider the following array:

``arr = [9, 2, 3, 4, -7, 3, 1, 3, 1, -4, -2, -2, 1, 7]``

For the target sum of 0, the maximum length subarray is:

``[3, 4, -7, 3, 1, 3, 1, -4, -2, -2]``

## Idea to Solve

To solve this problem efficiently, we can use a sliding window approach. We maintain two pointers, `start` and `end`, that represent the current subarray. We move the `end` pointer to the right while keeping track of the sum of elements between `start` and `end`. If the sum exceeds the target sum, we move the `start` pointer to the right. This way, we maintain a sliding window of subarrays and update the maximum length as we find longer subarrays that match the target sum.

## Pseudocode

``````function subarray_max(arr, size, sum):
start = 0
end = 0
current_sum = arr[0]
max_length = 0
max_start = 0

while end < size:
if current_sum < sum:
end++
if end < size:
current_sum += arr[end]
else:
current_sum -= arr[start]
start++

if current_sum = sum and (end - start + 1) > max_length:
max_length = end - start + 1
max_start = start

if max_length = 0:
print("No subarray found with the given sum.")
else:
print("Maximum length subarray with sum", sum, ":", end=" ")
for i from max_start to max_start + max_length - 1:
print(arr[i], end=" ")

// Example usage
arr = [9, 2, 3, 4, -7, 3, 1, 3, 1, -4, -2, -2, 1, 7]
size = size(arr)
sum = 0
subarray_max(arr, size, sum)``````

## Algorithm Explanation

1. The `subarray_max` function initializes the `start` and `end` pointers to the beginning of the array.
2. It maintains `current_sum` to track the sum of elements between `start` and `end`.
3. The algorithm moves the `end` pointer to the right and updates the `current_sum`.
4. If `current_sum` exceeds the target sum, the algorithm moves the `start` pointer to the right and updates `current_sum`.
5. If `current_sum` equals the target sum and the current subarray length is greater than the maximum length found so far, the algorithm updates `max_length` and `max_start`.
6. Finally, the algorithm prints the maximum length subarray with the target sum.

## Code Solution

``````//C Program
//Find max length subarray with given sum
#include <stdio.h>

void subarray_max(int arr[],int size ,int sum)
{
int count=0, i=0, j=0, k=0 , length=0;;

for(i=0; i < size; i++)
{

if(arr[i] == sum && length==0)
{
// When element is equal to given sum
// And subarray length is zero
// Then set initial length
length=1;
k=i;

}

count=arr[i];

for(j = i+1; j < size; j++)
{
//calculate Sum of subarray elements
count += arr[j];

//Determine whether given subarray is equal to given sum or not?
if(count == sum)
{

//Check given sum array length is higher or not of previous calculated length?
if(length < j-(i-1))
{
//When get of new sub array with new max length
//Get new length of subarray sub
length = j-(i-1);
//Get starting index of subarray of given sum
k = i;
}
}
}
}

printf("\n Total sum of %d are max subarray Length is :%d\n",sum,length );
for (i = k; i < k+length; ++i)
{
printf("%3d",arr[i] );
}
printf("\n");
}
int main()
{
//Defining collection array elements
int arr[] = {9,2, 3, 4, -7, 3, 1, 3, 1, -4, -2, -2 ,1, 7};

//Get the size of array
int size=(sizeof(arr)/sizeof(arr[0]));

//Given sum
int sum=0;

subarray_max(arr,size,sum);

return 0;
}```
```

#### Output

`````` Total sum of 0 are max subarray Length is :10
3  4 -7  3  1  3  1 -4 -2 -2``````
``````#include<iostream>

using namespace std;

/*
C++ Program
Find max length subarray with given sum
*/
class MyArray {
public:
void subarray_max(int arr[], int size, int sum) {
int count = 0, i = 0, j = 0, k = 0, length = 0;;
for (i = 0; i < size; i++) {
if (arr[i] == sum && length == 0) {
// When element is equal to given sum
// And subarray length is zero
// Then set initial length
length = 1;
k = i;
}
count = arr[i];
for (j = i + 1; j < size; j++) {
//calculate Sum of subarray elements
count += arr[j];
//Determine whether given subarray is equal to given sum or not?

if (count == sum) {
//Check given sum array length is higher or not of previous calculated length?

if (length < j - (i - 1)) {
//When get of new sub array with new max length
//Get new length of subarray sub
length = j - (i - 1);
//Get starting index of subarray of given sum
k = i;
}
}
}
}
cout << "\n Total sum of " << sum << " are max subarray Length is : " << length << "\n";
for (i = k; i < k + length; ++i) {
cout << " " << arr[i];
}
cout << "\n";
}
};
int main() {
MyArray obj ;
int arr[] = {
9,
2,
3,
4,
-7,
3,
1,
3,
1,
-4,
-2,
-2,
1,
7
};
//Count size of array
int size = sizeof(arr) / sizeof(arr[0]);
//Given sum
int sum = 0;
obj.subarray_max(arr, size, sum);
return 0;
}```
```

#### Output

`````` Total sum of 0 are max subarray Length is : 10
3 4 -7 3 1 3 1 -4 -2 -2``````
``````/*
Java Program
Find max length subarray with given sum
*/
public class MyArray {

public void subarray_max(int []arr,int size ,int sum)
{
int count=0, i=0, j=0, k=0 , length=0;;

for(i=0; i < size; i++)
{

if(arr[i] == sum && length==0)
{
// When element is equal to given sum
// And subarray length is zero
// Then set initial length
length=1;
k=i;

}

count=arr[i];

for(j = i+1; j < size; j++)
{
//calculate Sum of subarray elements
count += arr[j];

//Determine whether given subarray is equal to given sum or not?
if(count == sum)
{

//Check given sum array length is higher or not of previous calculated length?
if(length < j-(i-1))
{
//When get of new sub array with new max length
//Get new length of subarray sub
length = j-(i-1);
//Get starting index of subarray of given sum
k = i;
}
}
}
}

System.out.print("\n Total sum of "+sum+" are max subarray Length is : "+length+"\n" );
for (i = k; i < k+length; ++i)
{
System.out.print("  "+arr[i] );
}
System.out.print("\n");
}
public static void main(String[] args)
{

MyArray obj = new MyArray();
//Define array elements
int []arr =  {9,2, 3, 4, -7, 3, 1, 3, 1, -4, -2, -2 ,1, 7};
//Count size of array
int size=arr.length;

//Given sum
int sum=0;

obj.subarray_max(arr,size,sum);

}
}```
```

#### Output

`````` Total sum of 0 are max subarray Length is : 10
3 4 -7 3 1 3 1 -4 -2 -2``````
``````/*
C# Program
Find max length subarray with given sum
*/
using System;

public class MyArray {
public void subarray_max(int[] arr, int size, int sum) {
int count = 0, i = 0, j = 0, k = 0,length = 0;;
for (i = 0; i < size; i++) {
if (arr[i] == sum && length == 0) {
// When element is equal to given sum
// And subarray.Length is zero
// Then set initial.Length
length = 1;
k = i;
}
count = arr[i];
for (j = i + 1; j < size; j++) {
//calculate Sum of subarray elements
count += arr[j];
//Determine whether given subarray is equal to given sum or not?

if (count == sum) {
//Check given sum array.Length is higher or not of previous calculated.Length?

if (length < j - (i - 1)) {
//When get of new sub array with new max.Length
//Get new.Length of subarray sub
length = j - (i - 1);
//Get starting index of subarray of given sum
k = i;
}
}
}
}
Console.Write("\n Total sum of " + sum + " are max subarray.Length is : " +length + "\n");
for (i = k; i < k +length; ++i) {
Console.Write(" " + arr[i]);
}
Console.Write("\n");
}
public static void Main(String[] args) {
MyArray obj = new MyArray();
int[]
//Define array elements
arr = {
9,
2,
3,
4,
-7,
3,
1,
3,
1,
-4,
-2,
-2,
1,
7
};
//Count size of array
int size = arr.Length;
//Given sum
int sum = 0;
obj.subarray_max(arr, size, sum);
}
}```
```

#### Output

`````` Total sum of 0 are max subarray.Length is : 10
3 4 -7 3 1 3 1 -4 -2 -2``````
``````<?php
/*
Php Program
Find max length subarray with given sum
*/
class MyArray {
public  function subarray_max(\$arr, \$size, \$sum) {
\$count = 0;
\$i = 0;
\$j = 0;
\$k = 0;
\$length = 0;;
for (\$i = 0; \$i < \$size; \$i++) {
if (\$arr[\$i] == \$sum && \$length == 0) {
// When element is equal to given sum
// And subarray length is zero
// Then set initial length
\$length = 1;
\$k = \$i;
}
\$count = \$arr[\$i];
for (\$j = \$i + 1; \$j < \$size; \$j++) {
//calculate Sum of subarray elements
\$count += \$arr[\$j];
//Determine whether given subarray is equal to given sum or not?

if (\$count == \$sum) {
//Check given sum array length is higher or not of previous calculated length?

if (\$length < \$j - (\$i - 1)) {
//When get of new sub array with new max length
//Get new length of subarray sub
\$length = \$j - (\$i - 1);
//Get starting index of subarray of given sum
\$k = \$i;
}
}
}
}
echo("\n Total sum of ". \$sum ." are max subarray Length is : ". \$length ."\n");
for (\$i = \$k; \$i < \$k + \$length; ++\$i) {
echo(" ". \$arr[\$i]);
}
echo("\n");
}
}

function main() {
\$obj = new MyArray();
//Define array elements
\$arr = array(9, 2, 3, 4, -7, 3, 1, 3, 1, -4, -2, -2, 1, 7);
//Count size of array
\$size = count(\$arr);
//Given sum
\$sum = 0;
\$obj->subarray_max(\$arr, \$size, \$sum);

}
main();```
```

#### Output

`````` Total sum of 0 are max subarray Length is : 10
3 4 -7 3 1 3 1 -4 -2 -2``````
``````/*
Node Js Program
Find max length subarray with given sum
*/
class MyArray {
subarray_max(arr, size, sum) {
var count = 0;
var i = 0;
var j = 0;
var k = 0;
var length = 0;;
for (i = 0; i < size; i++) {
if (arr[i] == sum && length == 0) {
// When element is equal to given sum
// And subarray length is zero
// Then set initial length
length = 1;
k = i;
}
count = arr[i];
for (j = i + 1; j < size; j++) {
//calculate Sum of subarray elements
count += arr[j];
//Determine whether given subarray is equal to given sum or not?

if (count == sum) {
//Check given sum array length is higher or not of previous calculated length?

if (length < j - (i - 1)) {
//When get of new sub array with new max length
//Get new length of subarray sub
length = j - (i - 1);
//Get starting index of subarray of given sum
k = i;
}
}
}
}

process.stdout.write("\n Total sum of " + sum + " are max subarray Length is : " + length + "\n");
for (i = k; i < k + length; ++i) {
process.stdout.write(" " + arr[i]);
}

process.stdout.write("\n");
}
}

function main(args) {
var obj = new MyArray();
//Define array elements
var arr = [9, 2, 3, 4, -7, 3, 1, 3, 1, -4, -2, -2, 1, 7];
//Count size of array
var size = arr.length;
//Given sum
var sum = 0;
obj.subarray_max(arr, size, sum);
}

main();```
```

#### Output

`````` Total sum of 0 are max subarray Length is : 10
3 4 -7 3 1 3 1 -4 -2 -2``````
``````# Python 3 Program
# Find max length subarray with given sum
class MyArray :
def subarray_max(self, arr, size, sum) :
count = 0
i = 0
j = 0
k = 0
length = 0
i = 0
while (i < size) :
if (arr[i] == sum and length == 0) :
#  When element is equal to given sum
#  And subarray length is zero
#  Then set initial length
length = 1
k = i

count = arr[i]
j = i + 1
while (j < size) :
# calculate Sum of subarray elements
count += arr[j]
# Determine whether given subarray is equal to given sum or not?

if (count == sum) :
# Check given sum array length is higher or not of previous calculated length?

if (length < j - (i - 1)) :
# When get of new sub array with new max length
# Get new length of subarray sub
length = j - (i - 1)
# Get starting index of subarray of given sum
k = i

j += 1

i += 1

print("\n Total sum of ", sum ," are max subarray Length is : ", length ,"\n", end = "")
i = k
while (i < k + length) :
print(" ", arr[i], end = "")
i += 1

print("\n", end = "")

def main() :
obj = MyArray()
arr = [9, 2, 3, 4, -7, 3, 1, 3, 1, -4, -2, -2, 1, 7]
size = len(arr)
sum = 0
obj.subarray_max(arr, size, sum)

if __name__ == "__main__":
main()```
```

#### Output

`````` Total sum of  0  are max subarray Length is :  10
3  4  -7  3  1  3  1  -4  -2  -2``````
``````# Ruby Program
# Find max length subarray with given sum
class MyArray
def subarray_max(arr, size, sum)
count = 0
i = 0
j = 0
k = 0
length = 0
i = 0
while (i < size)
if (arr[i] == sum && length == 0)
#  When element is equal to given sum
#  And subarray length is zero
#  Then set initial length
length = 1
k = i
end
count = arr[i]
j = i + 1
while (j < size)
# calculate Sum of subarray elements
count += arr[j]
# Determine whether given subarray is equal to given sum or not?

if (count == sum)
# Check given sum array length is higher or not of previous calculated length?

if (length < j - (i - 1))
# When get of new sub array with new max length
# Get new length of subarray sub
length = j - (i - 1)
# Get starting index of subarray of given sum
k = i
end
end
j += 1
end
i += 1
end
print("\n Total sum of ", sum ," are max subarray Length is  :", length ,"\n")
i = k
while (i < k + length)
print(" ", arr[i])
i += 1
end
print("\n")
end
end
def main()
obj = MyArray.new()
arr = [9, 2, 3, 4, -7, 3, 1, 3, 1, -4, -2, -2, 1, 7]
size = arr.length
sum = 0
obj.subarray_max(arr, size, sum)
end
main()```
```

#### Output

`````` Total sum of 0 are max subarray Length is  :10
3 4 -7 3 1 3 1 -4 -2 -2
``````
``````/*
Scala Program
Find max length subarray with given sum
*/
class MyArray {
def subarray_max(arr: Array[Int], size: Int, sum: Int): Unit = {
var count: Int = 0;
var i: Int = 0;
var j: Int = 0;
var k: Int = 0;
var length: Int = 0;
i = 0;
while (i < size) {
if (arr(i) == sum && length == 0) {
// When element is equal to given sum
// And subarray length is zero
// Then set initial length
length = 1;
k = i;
}
count = arr(i);
j = i + 1;
while (j < size) {
//calculate Sum of subarray elements
count += arr(j);

//Determine whether given subarray is equal to given sum or not?

if (count == sum) {
//Check given sum array length is higher or not of previous calculated length?

if (length < j - (i - 1)) {
//When get of new sub array with new max length
//Get new length of subarray sub
length = j - (i - 1);

//Get starting index of subarray of given sum
k = i;
}
}
j += 1;
}
i += 1;
}
print("\n Total sum of " + sum + " are max subarray Length is : " + length + "\n");
i = k;
while (i < k + length) {
print(" " + arr(i));
i += 1;
}
print("\n");
}
}
object Main {
def main(args: Array[String]): Unit = {
val obj: MyArray = new MyArray();
val arr: Array[Int] = Array(9, 2, 3, 4, -7, 3, 1, 3, 1, -4, -2, -2, 1, 7);
val size: Int = arr.length;
val sum: Int = 0;
obj.subarray_max(arr, size, sum);
}
}```
```

#### Output

`````` Total sum of 0 are max subarray Length is : 10
3 4 -7 3 1 3 1 -4 -2 -2``````
``````/*
Swift Program
Find max length subarray with given sum
*/
class MyArray {
func subarray_max(_ arr: [Int], _ size: Int, _ sum: Int) {
var count: Int = 0;
var i: Int = 0;
var j: Int = 0;
var k: Int = 0;
var length: Int = 0;
i = 0;
while (i < size) {
if (arr[i] == sum && length == 0) {
// When element is equal to given sum
// And subarray length is zero
// Then set initial length
length = 1;
k = i;
}
count = arr[i];
j = i + 1;
while (j < size) {
//calculate Sum of subarray elements
count += arr[j];
//Determine whether given subarray is equal to given sum or not?

if (count == sum) {
//Check given sum array length is higher or not of previous calculated length?

if (length < j - (i - 1)) {
//When get of new sub array with new max length
//Get new length of subarray sub
length = j - (i - 1);
//Get starting index of subarray of given sum
k = i;
}
}
j += 1;
}
i += 1;
}
print("\n Total sum of ", sum ," are max subarray Length is : ", length ,"\n", terminator: "");
i = k;
while (i < k + length) {
print(" ", arr[i], terminator: "");
i += 1;
}
print("\n", terminator: "");
}
}
func main() {
let obj: MyArray = MyArray();
let arr: [Int] = [9, 2, 3, 4, -7, 3, 1, 3, 1, -4, -2, -2, 1, 7];
let size: Int = arr.count;
let sum: Int = 0;
obj.subarray_max(arr, size, sum);
}
main();```
```

#### Output

`````` Total sum of  0  are max subarray Length is :  10
3  4  -7  3  1  3  1  -4  -2  -2``````

## Time Complexity

The algorithm iterates through the array once, moving both the `start` and `end` pointers. Therefore, the time complexity is linear, `O(n)`, where `n` is the size of the array.

## Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

Categories
Relative Post