Quantum sensors can show unprecedented sensitivities, provided they are controlled in a very specific, optimal way. Here, we consider a spin sensor of time-varying fields in the presence of dephasing noise, and we show that the problem of finding the optimal pulsed control field can be mapped to the determination of the ground state of a spin chain. We find an approximate but analytic solution of this problem, which provides a \emph{lower bound} for the sensor sensitivity, and a pulsed control very close to optimal, which we further use as initial guess for realizing a fast simulated annealing algorithm. We experimentally demonstrate the sensitivity improvement for a spin-qubit magnetometer based on a nitrogen-vacancy center in diamond.