Maps with Me works with Open Street Maps, which is completely unusable in Japan for finding addresses. So I wouldn't bother bringing that one.

I find Google Maps is a lifesaver for helping me find my way around, and I've lived in Tokyo for years. It helps you figure out which subway or train is best to take, which is not always the one you'd expect.