title: Length of largest substring adds up to S
body: <p>I was asked the following question in an interview and I couldn't give the optimal answer to this.</p>
  
  <p>Problem: Write a program that can find the length of the largest contiguous sub-array that sums up to S. Given an array of variable size and an Integer.</p>
  
  <p>Input: 1. An array of variable size, which can have only {-1, 0, 1} elements. </p>
  
  <p>Example: A[] = {1, 0, 0, 1, -1, 1, 1, 1, 1}</p>
  
  <ol start="2">
  <li>An integer S, </li>
  </ol>
  
  <p>Example: S = 4</p>
  
  <p>Output: 8</p>
  
  <p>Explanation: Largest contiguous sub-array of A that adds up to S=4: {1, 0, 0, 1, -1, 1, 1, 1} or {0, 0, 1, -1, 1, 1, 1, 1}</p>
  
  <p>Constraint: Should complete in O(N)</p>
  
  <p>I have solved the problem, but couldn't meet the time complexity. Can anyone help with a solution that can solve this in O(N).</p>
  
  <p>PS: No Copyright issues with the question that I have asked.</p>