title: How to find contiguous subarray of integers in an array from n arrays such that the sum of elements of such contiguous subarrays is minimum
body: <p>Input: n arrays of integers of length p.</p>
  <p>Output: An array of p integers built by copying contiguous subarrays of the input arrays into matching indices of the output, satisfying the following conditions.</p>
  <ul>
  <li>At most one subarray is used from each input array.</li>
  <li>Every index of the output array is filled from exactly one subarray.</li>
  <li>The output array has the minimum possible sum.</li>
  </ul>
  <p>Suppose I have 2 arrays:</p>
  <p><code>[1,7,2]</code></p>
  <p><code>[2,1,8]</code></p>
  <p>So if I choose a subarray <code>[1,7]</code> from array 1 and subarray <code>[8]</code> from array 2. since these 2 subarrays are not overlapping for any index and are contiguous. We are also not taking any subarray twice from an array from which we have already chosen a subarray.</p>
  <p>We have the number of elements in the arrays inside the collection = <code>2 + 1 = 3</code>, which is the same as the length of the individual array (i.e. <code>len(array 1) which is equal to 3</code>). So, this collection is valid.</p>
  <p>The sum here for <code>[1,7]</code> and <code>[8]</code> is <code>1 + 7 + 8 = 16</code></p>
  <p>We have to find a collection of such subarrays such that the total sum of the elements of subarrays is minimum.</p>
  <p>A solution to the above 2 arrays would be a collection <code>[2,1]</code> from array 1 and <code>[2]</code> from array 2.
  This is a valid collection and the sum is <code>2 + 1 + 2 = 5</code>  which is the minimum sum for any such collection in this case.</p>
  <p>I cannot think of any optimal or correct approach, so I need help.</p>
  <p>Some Ideas:</p>
  <p>I tried a greedy approach by choosing minimum elements from all array for a particular index since the index is always increasing (non-overlapping)  after a valid choice, I don't have to bother about storing minimum value indices for every array. But this approach is clearly not correct since it will visit the same array twice.</p>
  <p>Another method I thought was to start from the 0th index for all arrays and start storing their sum up to <code>k</code> elements for every array since the no. of arrays are finite, I can store the sum upto <code>k</code> elements in an array. Now I tried to take a minimum across these sums and for a &quot;minimum sum&quot;, the corresponding subarray giving this sum (i.e. <code>k</code> such elements in that array) can be a candidate for a valid subarray of size <code>k</code>, thus if we take this subarray, we can add a <code>k + 1</code>-th element corresponding to every array into their corresponding sum and if the original minimum still holds, then we can keep on repeating this step. When the minima fail, we can consider the subarray up to the index for which minima holds and this will be a valid starting subarray.  However, this approach will also clearly fail because there could exist another subarray of <code>size &lt; k</code> giving minima along with remaining index elements from our subarray of size k.</p>
  <p>Sorting is not possible either, since if we sort then we are breaking consecutive condition.</p>
  <p>Of course, there is a brute force method too.</p>
  <p>I am thinking, working through a greedy approach might give a progress in the approach.</p>
  <p>I have searched on other Stackoverflow posts, but couldn't find anything which could help my problem.</p>