Some comments found around the net pertaining to the matches, doesn't looks like there are guaranteed strategies, just tactics that should be employed:
For Impossible, remember that you get a health percentage bonus depending on what you do during your fights. You always get at least a 25% health bonus too. Here are some requirements:
Performing a 30% Combo
Winning a Clash
Using an Interactive Object
As well as other factors. You can get a 45-50% health bonus from those above. Try performing these every fight to keep your health as high as possible. Obviously you'll want to use the Doomsday method mentioned above and beware of characters that give him the most trouble such as The Flash, Green Lantern, Lex, and Superman. If the CPU isn't falling for your combo be sure to pause and attack them when you see an opening, usually crouching heavy attack up close. Usually you lose track of health toward the middle but if you have a few good matches with safe pausing techniques you an slowly earn it back. It's all about being careful really. And use your Super Meter wisely, it carries over like your health. Use it to win clashes, Super Moves are not necessary unless you're losing badly.
I also used Doomsday pre-patch for The Max and jumping down+A, X X Y is all you need together with the Meter Burn version of down, back + Y. The A.I. won't block or dodge this pre-patch 90 percent of the time so make sure to use it. The block damage of the last Y attack is just insane and wil add up over time.
The only things that bothered me were the characters I got. As long as I got Green Arrow, Green Lantern, Lex Luthor and Aquaman, I restarted. Batman kicked my butt at stage 10 two times due to his counter move, so make sure that he isn't one of the last in the roster.
Other than that the A.I. really isn't clever. I abused respawning interactibles like mad when I had the chance. As long as you walk slowly backbard the A.I. will follow you and walk into the interactibles most of the time. Patience and luck is all you need here. Took me around 6-7 hours for The Max alone while I beat Impossible on my first try.
How on earth are you supposed to beat the AI on max difficulty without trying? I can barely do that WITH retrying. The AI constantly reads your inputs and reacts so it's extremely hard. Anyone got any tips?
-DD supernova spam and armor. Deathstroke gun spam. Superman air heat vision spam. Also, abuse dat meter.
-Try command grab characters.