  In this paper, we present a thorough study of maximizing a regularized
non-monotone submodular function subject to various constraints, i.e., $\max \{
g(A) - \ell(A) : A \in \mathcal{F} \}$, where $g \colon 2^\Omega \to
\mathbb{R}_+$ is a non-monotone submodular function, $\ell \colon 2^\Omega \to
\mathbb{R}_+$ is a normalized modular function and $\mathcal{F}$ is the
constraint set. Though the objective function $f := g - \ell$ is still
submodular, the fact that $f$ could potentially take on negative values
prevents the existing methods for submodular maximization from providing a
constant approximation ratio for the regularized submodular maximization
problem. To overcome the obstacle, we propose several algorithms which can
provide a relatively weak approximation guarantee for maximizing regularized
non-monotone submodular functions. More specifically, we propose a continuous
greedy algorithm for the relaxation of maximizing $g - \ell$ subject to a
matroid constraint. Then, the pipage rounding procedure can produce an integral
solution $S$ such that $\mathbb{E} [g(S) - \ell(S)] \geq e^{-1}g(OPT) -
\ell(OPT) - O(\epsilon)$. Moreover, we present a much faster algorithm for
maximizing $g - \ell$ subject to a cardinality constraint, which can output a
solution $S$ with $\mathbb{E} [g(S) - \ell(S)] \geq (e^{-1} - \epsilon) g(OPT)
- \ell(OPT)$ using $O(\frac{n}{\epsilon^2} \ln \frac 1\epsilon)$ value oracle
queries. We also consider the unconstrained maximization problem and give an
algorithm which can return a solution $S$ with $\mathbb{E} [g(S) - \ell(S)]
\geq e^{-1} g(OPT) - \ell(OPT)$ using $O(n)$ value oracle queries.
