Largest sum divisible by n
Here are a few random ideas:


The dynamic-programming algorithm can be flipped to look for a smallest sum instead of a largest sum. You just end up looking for a sum congruent to the remainder of the sum of the entire array, instead of one congruent to zero. If we process the elements in increasing order, this sometimes allows the dynamic algorithm to terminate before processing the entire array.

The cost would be $O(n k)$ if we processed $k$ elements. There's not a lower bound of $\Omega(n \log n)$ on this algorithm because we don't have to sort all the elements. It only takes $O(n \log k)$ time to get the $k$ smallest elements.
If we cared about the set with the larget size, instead of the set with the largest sum, we might be able to use fast-fourier-transform-based polynomial multiplication to solve the problem in $O(n (\log n)^2 (\log \log n))$ time. Similar to what's done in 3SUM when the domain range is limited. (Note: use repeated squaring to do a binary search, else you'll get $O(n k (\log n) (\log \log n))$ where $k$ is the number of omitted elements.)
When $n$ is composite, and almost all remainders are a multiple of one of $n$'s factors, significant time might be saved by focusing on the remainders that aren't a multiple of that factor.
When a remainder r is very common, or there are only a few remainders present, keeping track of 'next open slot if you start from here and keep advancing by r' information can save a lot of scanning-for-jumps-into-open-spots time.
You can shave a log factor by only tracking reachability and using bit masks (in the flipped dynamic algorithm), then backtracking once you reach the target remainder.
The dynamic programming algorithm is very amenable to being run in parallel. With a processor for each buffer slot you can get down to $O(n)$. Alternatively, by using $O(n^2)$ breadth, and divide and conquer aggregation instead of iterative aggregation, the circuit depth cost can get all the way down to $O(\log^2 n)$.
(Meta) I strongly suspect that the problem you were given is about contiguous sums. If you linked to the actual problem, it would be easy to verify that. Otherwise I'm very surprised by how difficult this problem is, given that it was assigned in a course called "Introduction to Algorithms". But maybe you covered a trick in class that makes it trivial.