Hydrocodes are necessary numerical tools in the fields of implosion and high-velocity impact, which often involve large deformations with changing-topology interfaces. It is very difficult for Lagrangian or Simplified Arbitrary Lagrangian-Eulerian (SALE) codes to tackle these kinds of large-deformation problems, so a staggered Multi-Material ALE (MMALE) code is developed in this paper, which is the explicit time-marching Lagrange plus remap type. We use the Moment Of Fluid (MOF) method to reconstruct the interfaces of multi-material cells and present an adaptive bisection method to search for the global minimum value of the nonlinear objective function. To keep the Lagrangian computations as long as possible, we develop a robust rezoning method named as Combined Rezoning Method (CRM) to generate the convex, smooth grids for the large-deformation domain. Regarding the staggered remap phase, we use two methods to remap the variables of Lagrangian mesh to the rezoned one. One is the first-order intersection-based remapping method that doesn't limit the distances between the rezoned and Lagrangian meshes, so it can be used in the applications of wide scope. The other one is the conservative second-order flux-based remapping method developed by Kucharika and Shashkov [22] that requires the rezoned element to locate in its adjacent old elements. Numerical results of triple point problem show that the result of first-order remapping method using ALE computations is gradually convergent to that of second-order remapping method using Eulerian computations with the decrease of rezoning, thereby telling us that MMALE computations should be performed as few as possible to reduce the errors of the interface reconstruction and the remapping. Numerical results provide a clear evidence of the robustness and the accuracy of this MMALE scheme, and that our MMALE code is powerful for the large-deformation problems.