title: Find a subarray whose sum is divisible by a number K the subarray should be of maximum sum of all possible subarrays
body: <p>I have been practising algorithmic questions and I came across this one.<br>
  Given an array(of both +ve and -ve) numbers, I have to find a contiguous subarray such that, the sum is divisible by any number K, and the subarray should be of possibly maximum sum. For eg.<br>
  <code>a={1,2,2,1,1,4,5,3}</code> and <code>k=5</code> and the maximum sum subarray divisible by k would be<br>
  <code>{2,2,1,1,4,5}, sum = 15</code><br>
  Presently all I can think of is, each element is having two possibilities, either include it in the target subarray or not. But this would be an exponential algorithm.<br>
  EDIT: is it possible to solve this in Linear Time. Please Help</p>