Try the Nuclear Option, a "DFU restore to a New Phone" per @robnbill's suggestion. Re: Re: Battery problem after update to IOS 9.3.1 It is not sufficient to erase all content. It is not sufficient to reset all settings. It is not sufficient to erase and restore from your most recent backup. It is not sufficient to try the usual "power saving" suggestions. And it even an update to iOS 10.x has no effect. Apparently there's something in Cloud settings from pre-9.3.1 iOS versions that when it meets 9.3.x has indigestion. Sorry.
It worked for me. I reported my initial findings in the immediately preceding post (page 10 of this thread). I promised an update. I have been slow to restore my software. I am only about half done restoring software, photos, and albums. But so far, I can go the entire day and use no more than 30% to 40% of my battery, even enabling background execution and location services that I had disabled in the misguided hope that I'd save some energy.
Good luck. Please report your results.