Android - Why does this ad keep showing up below my notification bar and how do I stop it?

There are many complaints about the Premium Wallpapers HD app, which apparently started to show ads looking like this after its latest update.

In general, an Android app can draw anything over other apps if it has the “Draw over other apps” permission, so you can check which of your installed apps have this permission.