Buenas, yo me base en la documentación oficial de google:
https://developers.google.com/maps/documentation/android-api/signup
He hice algo parecido a lo que menciona @Andhii1293
Android tiene varios certificados para las firmas digitales uno por ejemplo el keystore.debug guardado en la carpeta de tu app tu segurametnes hayas obtenido una clave api firmada con esta keystore, tu necesitas firmarla con la misma keystore con la que firmas la app, yo hice esto:
1.- Abres la consola de desarrollador de google, creas un nuevo proyecto ( da igual que ya tuvieras uno, lo creas de nuevo), habilitas la api de google maps.
2.- vas a credenciales, nueva clave api y selecionas android key
3.- Abres cmd y te mueves a donde guardas la keystore definitiva para firmas tus apps y pones la siguiente linea.
keytool -list -v -keystore nombre_keystore -alias alias_keystore -storepass pass_store-keypass pass_key
4.- Copias el fingerprint SHA1, y lo pegas en la web que abrimos en el paso 2, y a la izquierda tienes otro input donde debes meter el paquete completo de tu app, lo encotnraras en tu manifest.xml, guardas y listo.
5.- Te vas a tu manifest.xml y antes de que acabe el tag </application> pegas esto:
<meta-data
android:name="com.google.android.geo.API_KEY"
android:value="API_KEY">
Sustituyes android:value="API_KEY" por la api que te a dado google y listo, firmas la app con el keystore que usaste en el paso 3 y ya te funcionan los mapas.
espero que te sirva.