Linear response theory for the density matrix renormalization group (DMRG-LRT) was first presented in terms of the DMRG renormalization projectors [J. J. Dorando, J. Hachmann, and G. K.-L. Chan, J. Chem. Phys. 130, 184111 (2009)]. Later, with an understanding of the manifold structure of the matrix product state (MPS) ansatz, which lies at the basis of the DMRG algorithm, a way was found to construct the linear response space for general choices of the MPS gauge in terms of the tangent space vectors [J. Haegeman, J. I. Cirac, T. J. Osborne, I. Pižorn, H. Verschelde, and F. Verstraete, Phys. Rev. Lett. 107, 070601 (2011)]. These two developments led to the formulation of the Tamm-Dancoff and random phase approximations (TDA and RPA) for MPS. This work describes how these LRTs may be efficiently implemented through minor modifications of the DMRG sweep algorithm, at a computational cost which scales the same as the ground-state DMRG algorithm. In fact, the mixed canonical MPS form implicit to the DMRG sweep is essential for efficient implementation of the RPA, due to the structure of the second-order tangent space. We present ab initio DMRG-TDA results for excited states of polyenes, the water molecule, and a [2Fe-2S] iron-sulfur cluster.