I finally got The Max.
First thing I did was delete all of my bonus content. I got rid of all my characters, all my costume pieces, all my STARS labs missions until it was just my saved game. Playing Vanilla Injustice.
I used Doomsday and I reset the roster until I didn't have Green Lantern, Batman or Lex Luthor, everyone else I was able to beat (though Wonder Woman is kinda tough).
Then each fight all I did was jump in Down + Heavy in the air, then Light, Light, Medium (JD+3, 112). Like everyone else says the last medium in the string does massive chip damage on block, which is what the computer does most of the time.
You want to fight zoners like Sinestro and Deathstroke. Yeah they can still destroy you, but more often then not you will be able to beat them.
The best tip is to learn what they do. The computer is an idiot, more so on very hard then anything else. They will more often then not do the same thing to punish what you do over and over again. Once you know your opponent you will be able to predict what they will do. What this means is that you will spend hours losing, because you need to try different things to see how the computer reacts. Its ok to lose a lot, because you only need to win once
Now for zoners (sinestro, deathstroke, raven, harley, cyborg) what you do is stay very close to them. When you knock them down with a combo you dash forward to be right on top of them. When you jump and do the down heavy you will cross them up (where your feet hit them in the head) and you can do your combo again.
For everyone else you need to trick them. Most characters will fall for the air down heavy a lot of the time, people like Ares, Flash, and Wonder Woman are tricky, but what I found out is if you do nothing, the computer doesn't know how to react.
Example. My last fight was against Nightwing. Now Nightwing is a jerk and will do a 18 hit combo on you every change he gets. What i ended up doing was after a knock down I would dash up and do nothing. As he stood up the computer was already reacting to me doing nothing with an attack so I would then jump and down heavy. Most of the time it would work. I even got him in the corner and would just neutral jump (jump straight up in the air and not push a button) which would freak them out even more because they don't understand how to react to nothing, and then hit down heavy. It would work on Aquaman as well.
It takes time to learn how fast a character gets up to know when to jump, but once you do learn the timing it turns out to be really easy. Not Zangief's spinning lariat easy, but just let me say The Max made me so mad I punched myself in the face, and when I beat it the matches went like butter and not a single fight was a problem.