Finding maximum using DFT
This sounds like a good candidate for the Sparse Fast Fourier Transform (sFFT). Have a look at H. Hassanieh, P. Indyk, D. Katabi, and E. Price, sFFT: Sparse Fast Fourier Transform, 2012. I don't know details of the algorithm. You have the domains swapped, which should be fine as the discrete Fourier transform (DFT) and its inverse (IDFT) are nearly identical.

sFFT has been discussed also here on dsp.stackexchange.com.