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.

New Comment