The Mars Science Laboratory (MSL) Rover Environmental Monitoring Station (REMS) has now made continuous in-situ meteorological measurements for several martian years at Gale crater, Mars. Of importance in the search for liquid formation are REMS' measurements of ground temperature and in-air measurements of temperature and relative humidity, which is with respect to ice. Such data can constrain the surface and subsurface stability of brines. Here we use updated calibrations to REMS data and consistent relative humidity comparisons (i.e., w.r.t. liquid vs w.r.t. ice) to investigate the potential formation of surface and subsurface liquids throughout MSL's traverse. We specifically study the potential for the deliquescence of calcium perchlorate. Our data analysis suggests that surface brine formation is not favored within the first 1648 sols as there are only two times (sols 1232 and 1311) when humidity-temperature conditions were within error consistent with a liquid phase. On the other hand, modeling of the subsurface environment would support brine production in the shallow subsurface. Indeed, we find that the shallow subsurface for terrains with low thermal inertia ($\Gamma\lesssim 300$ J m$^{-2}$ K$^{-1}$ s$^{-1/2}$) may be occasionally favorable to brine formation through deliquescence. Terrains with $\Gamma\lesssim175$ J m$^{-2}$ K$^{-1}$ s$^{-1/2}$ and albedos of $\gtrsim0.25$ are the most apt to subsurface brine formation. Should brines form, they would occur around Ls 100$^{\circ}$. Their predicted properties would not meet the Special nor Uncertain Region requirements, as such they would not be potential habitable environments to life as we know it.