Find the longest contiguous subsequence such that its sum $(a_i + a_{i+1} + \cdots + a_j)$ is divisible by $D$
There exists a linear time algorithm.   


Compute partial sum $s_j = \sum_{i=1}^j a_i$ and their remainders $r_j = s_j \mod D$.  
Consider the sequence $\{(j,s_j,r_j)\}_{j=0}^N$.  For each $0\leq r &lt; D$, compute the subsequence consisting of all tuple $(j,s_j,r_j)$ such that $r_j  = r$.  An easy approach is to sort the tuples in the sequence by their third component, using an stable sorting algorithm ($O(N \log N)$ time).  In this problem, $D \approx N$, so we could use bucket sort, improving the running time to linear; otherwise, using hash could also improve the running time to linear.
For each subsequence, apply the following algorithm on it.  


Pick two pointer $i,j$, both initialized as the first element in the 
subsequence.  
If $s_j - s_i &gt; DM$, point $j$ to the successor of $(j,s_j,r_j)$ in the subsequence, otherwise point $i$ to the successor of $(i,s_i,r_i)$ in the subsequence.  
Repeat step 2 until $j$ points to the last element in the sequence. 


Among all temporary values of $(i,j)$, find one that maximize $j-i$ under constraint $s_j-s_i \leq DM$.