title: Maximum subarray sum modulo M
body: <p>Most of us are familiar with the <a href="http://www.geeksforgeeks.org/largest-sum-contiguous-subarray/">maximum sum subarray problem</a>. I came across a variant of this problem which asks the programmer to output the maximum of all subarray sums modulo some number M. </p>
  
  <p>The naive approach to solve this variant would be to find all possible subarray sums (which would be of the order of N^2 where N is the size of the array). Of course, this is not good enough. The question is - how can we do better?  </p>
  
  <p>Example: Let us consider the following array:</p>
  
  <p>6 6 11 15 12 1 </p>
  
  <p>Let M = 13. In this case, subarray 6 6 (or 12 or 6 6 11 15 or 11 15 12) will yield maximum sum ( = 12 ). </p>