Construction of maximal entanglement-assisted quantum error correction (EAQEC) codes is one of the fundamental problems of quantum computing and quantum information. The objective of this paper is twofold: firstly, to obtain all possible construction matrices of the linear codes over the skew group ring \({\mathbb {F}}_4 \rtimes _{\varphi } G,\) where G is the cyclic and dihedral groups of finite orders; and secondly, to obtain some good maximal EAQEC codes over the finite field \({\mathbb {F}}_4\) by using skew construction matrices. Additionally, to speed up the computational search time, we employ a nature inspired heuristic optimisation algorithm, the virus optimisation (VO) algorithm. With our method, we obtain a number of good maximal EAQEC codes over the finite field \({\mathbb {F}}_4\) in a reasonably short time. In particular, we improve the lower bounds of 18 maximal EAQEC codes that exist in the literature. Moreover, some of our EAQEC codes turn out to be also maximum distance separable (MDS) codes. Also, by using our construction matrices, we provide counterexamples to Theorems 4 and 5 of Lai et al. (Quantum Inf Process 13(4):957–990, 2014), on the non-existence of maximal EAQEC codes with parameters \([[n, 1, n; n-1]]\) and \([[n, n-1, 2;1]]\) for an even length n. We also give a counterexample to another Theorem found in Lai and Ashikhmin (IEEE Trans Inf Theory 64:(1), 622–639, 2018), which states that there is no entanglement-assisted stabilizer code with parameters \([[4, 2, 3;2]]_4.\)
