Faits :
A.
Au mois de novembre 2005, X._, ressortissant algérien né en 1976, a déposé une demande d'asile en Suisse sous une fausse identité. Cette demande a été rejetée le 21 février 2006. L'intéressé n'a pas quitté la Suisse, malgré le renvoi prononcé à son encontre.
Le 18 novembre 2009, X._ a reconnu être le père d'un enfant né le 7 février 2009 d'une mère suisse. Il a épousé celle-ci le 7 août 2010 et, le 25 janvier 2011, il a été mis au bénéfice d'une autorisation de séjour au titre du regroupement familial. Le couple vit séparé, au plus tôt depuis le mois de décembre 2014.
Durant ses années de présence en Suisse, X._ a été condamné à 17 reprises pour des infractions de toutes sortes, la dernière fois le 20 février 2018 à 90 jours-amende pour infraction à la LStup (RS 812.121). Sa condamnation la plus importante, prononcée le 17 mai 2010, était de 30 mois de peine privative de liberté pour crime contre la LStup, délit contre la LStup, contravention à la LStup, recel, séjour illégal, délit contre la LSEE (depuis le 1 er janvier 2008 la LEtr; actuellement la LEI; RS 142.20), induction de la justice en erreur, violation des règles de la circulation routière et dénonciation calomnieuse.
B.
Le 29 mars 2016, le Service des migrations de la République et canton de Neuchâtel (ci-après: le Service des migrations) a informé X._ qu'il était favorable à la prolongation de son autorisation séjour et a transmis le dossier au Secrétariat d'Etat aux migrations (ci-après: le Secrétariat d'Etat) pour qu'il donne son approbation. Par décision du 17 août 2016, le Secrétariat d'Etat a refusé d'approuver la prolongation de l'autorisation de séjour de X._. Celui-ci a contesté cette décision le 16 septembre 2016 auprès du Tribunal administratif fédéral qui, par arrêt du 9 octobre 2018, a rejeté le recours.
C.
Agissant par la voie du recours en matière de droit public et celle, subsidiaire, du recours constitutionnel, X._ demande au Tribunal fédéral, sous suite de frais et dépens, d'annuler l'arrêt du Tribunal administratif fédéral du 9 octobre 2018 et de prolonger ( recte d'approuver la prolongation de) son autorisation de séjour.
Le Tribunal administratif fédéral renonce à se déterminer. Le Secrétariat d'Etat conclut au rejet du recours.

Considérant en droit :
1.
1.1. D'après l'art. 83 let. c ch. 2 LTF, le recours en matière de droit public est irrecevable contre les décisions en matière de droit des étrangers qui concernent une autorisation à laquelle ni le droit fédéral ni le droit international ne donnent droit. Selon la jurisprudence, il suffit qu'il existe un droit potentiel à l'autorisation, étayé par une motivation soutenable, pour que cette clause d'exclusion ne s'applique pas et, partant, que la voie du recours en matière de droit public soit ouverte. La question de savoir si les conditions d'un tel droit sont effectivement réunies relève du fond (<ref-ruling> consid. 1.1 p. 332 et les références). En l'occurrence, du moment que le recourant est père d'un enfant mineur de nationalité suisse et vit séparé d'une ressortissante suisse, les art. 50 LEI et 8 CEDH sont potentiellement de nature à lui conférer un droit à une autorisation de séjour. Le recours en matière de droit public et ainsi ouvert. Le recours constitutionnel subsidiaire doit quant à lui être déclaré irrecevable, cette voie de droit n'étant pas ouverte contre les arrêts du Tribunal administratif fédéral (<ref-law> a contrario).
1.2. Au surplus, le recours est dirigé contre une décision finale (<ref-law>) rendue dans une cause de droit public (<ref-law>) par le Tribunal administratif fédéral (<ref-law>). Déposé dans le délai (<ref-law>) et la forme (<ref-law>) prévus par la loi, le recours est en principe recevable.
2.
Le Tribunal fédéral statue en principe sur la base des faits établis par l'autorité précédente (<ref-law>), sous réserve des cas prévus à l'<ref-law> (<ref-ruling> consid. 4.4.3 p. 156). Le recourant ne peut critiquer les constatations de fait ressortant de la décision attaquée que si celles-ci ont été effectuées en violation du droit au sens de l'<ref-law> ou de manière manifestement inexacte, c'est-à-dire arbitraire, et si la correction du vice est susceptible d'influer sur le sort de la cause (<ref-law>; <ref-ruling> consid. 6 p. 358). Conformément à l'<ref-law>, le recourant doit expliquer de manière circonstanciée en quoi ces conditions seraient réalisées. Les faits invoqués de manière appellatoire sont irrecevables (<ref-ruling> consid. 6.3 p. 375). Par ailleurs, aucun fait nouveau ni preuve nouvelle ne peut en principe être présenté devant le Tribunal fédéral (<ref-law>).
En l'occurrence, dans la mesure où le recourant se prévaut de manière très générale d'établissement inexact des faits, il ne saurait être suivi. Il ne motive en effet pas à suffisance son grief, se contentant de présenter ses propres vision et appréciation des faits et de les opposer à celles de l'autorité précédente. Une telle manière de faire ne saurait être admise. Dans ces conditions, le Tribunal fédéral examinera le recours sur la seule base des faits retenus par le Tribunal administratif fédéral dans l'arrêt entrepris.
3.
Le recourant se plaint d'une violation de l'art. 50 LEI, expliquant que son union conjugale a duré plus de trois ans, que son intégration est réussie (ancien art. 50 al. 1 let. a LEtr [RO 2007 5437], cf. art. 126 al. 1 LEI) et que la poursuite de son séjour en Suisse s'impose pour des raisons personnelles majeures (art. 50 al. 1 let. b LEI, notamment en relation avec l'art. 8 CEDH), en raison de la présence en suisse de son fils. Le recourant vivant séparé d'une ressortissante suisse, c'est à juste titre qu'il n'invoque pas l'art. 42 al. 1 LEI, qui prévoit notamment que le conjoint d'un ressortissant suisse a droit à l'octroi d'une autorisation de séjour et à la prolongation de sa durée de validité à condition de vivre en ménage commun avec lui.
4.
4.1. Selon l'ancien art. 50 al. 1 let. a LEtr, après dissolution de la famille, le droit du conjoint et des enfants à l'octroi d'une autorisation de séjour et à la prolongation de sa durée de validité en vertu des anciens art. 42 et 43 LEtr subsiste si l'union conjugale a duré au moins trois ans et l'intégration est réussie. Le principe de l'intégration doit permettre aux étrangers dont le séjour est légal et durable de participer à la vie économique, sociale et culturelle de la Suisse (art. 4 al. 2 LEI). D'après l'art. 77 al. 4 de l'ordonnance du 24 octobre 2007 relative à l'admission, au séjour et à l'exercice d'une activité lucrative (OASA; RS 142.201), un étranger s'est bien intégré, au sens de l'ancien art. 50 al. 1 let. a LEtr, notamment lorsqu'il respecte l'ordre juridique suisse et les valeurs de la Constitution fédérale (let. a) et qu'il manifeste sa volonté de participer à la vie économique et d'apprendre la langue nationale parlée au lieu de domicile (let. b). Selon l'art. 4 de l'ordonnance du 24 octobre 2007 sur l'intégration des étrangers (OIE; RS 142.205), la contribution des étrangers à l'intégration se manifeste notamment par le respect de l'ordre juridique et des valeurs de la Constitution fédérale (let. a), par l'apprentissage de la langue nationale parlée sur le lieu de domicile (let. b), par la connaissance du mode de vie suisse (let. c) et par la volonté de participer à la vie économique et d'acquérir une formation (let. d). L'adverbe "notamment", qui est employé tant à l'art. 77 al. 4 OASA qu'à l'<ref-law>, illustre le caractère non exhaustif des critères d'intégration qui sont énumérés par ces dispositions et met aussi en exergue le fait que la notion "d'intégration réussie" doit s'examiner à l'aune d'une appréciation globale des circonstances. Dans l'examen de ces critères d'intégration, les autorités compétentes disposent d'un large pouvoir d'appréciation que le Tribunal fédéral ne revoit qu'avec retenue (cf. anciens art. 54 al. 2 et 96 al. 1 LEtr et <ref-law>; arrêt 2C_301/2018 du 24 septembre 2018 consid. 3.2 et les références).
Selon la jurisprudence, il n'y a pas d'intégration réussie lorsque l'étranger n'exerce pas d'activité lucrative qui lui permette de couvrir ses besoins et qu'il dépend des prestations sociales pendant une période relativement longue. A l'inverse, le fait pour une personne de ne pas avoir commis d'infractions pénales et de pourvoir à son revenu sans recourir à l'aide sociale ne permet pas à lui seul de retenir une intégration réussie. Des périodes d'inactivité de durée raisonnable n'impliquent pas forcément une absence d'intégration professionnelle. Il n'est pas indispensable que l'étranger fasse montre d'une carrière professionnelle requérant des qualifications spécifiques; l'intégration réussie au sens de l'ancien art. 50 al. 1 let. a LEtr n'implique en effet pas nécessairement la réalisation d'une trajectoire professionnelle particulièrement brillante au travers d'une activité exercée sans discontinuité. L'essentiel en la matière est que l'étranger subvienne à ses besoins, n'émarge pas à l'aide sociale et ne s'endette pas de manière disproportionnée. L'intégration réussie d'un étranger qui est actif professionnellement en Suisse, dispose d'un emploi fixe, a toujours été financièrement indépendant, se comporte correctement et maîtrise la langue locale ne peut être niée qu'en la présence de circonstances particulièrement sérieuses. L'absence de liens sociaux très étroits en Suisse n'exclut pas non plus d'emblée l'existence d'une intégration réussie, de même que l'absence de vie associative (pour tout ce qui précède, cf. arrêts 2C_301/2018 du 24 septembre 2018 consid. 3.2 et les références; 2C_14/2014 du 27 août 2014 consid. 4.6.1, non publié in <ref-ruling>).
4.2. En l'occurrence, si le recourant se trouve depuis quatorze ans en Suisse, il ne faut pas perdre de vue qu'il y a vécu durant de nombreuses années dans l'illégalité. Surtout, comme l'a retenu à juste titre l'autorité précédente, durant sa présence en Suisse, le recourant a connu plusieurs périodes de chômage et n'a exercé qu'épisodiquement une activité lucrative. Il n'a en effet produit que deux certificats de travail faisant état d'une activité à temps partiel entre août 2012 et mars 2013 et d'un emploi occupé entre septembre et décembre 2015. S'il a conclu un contrat de travail le 18 janvier 2017 pour une activité dans un bar, il n'a cependant fourni aucune information complémentaire à l'autorité précédente, malgré les demandes de celle-ci. A cette faible intégration professionnelle s'ajoute une situation financière précaire. En 2018, le recourant présentait pour près de 30'000 fr. de poursuites, ainsi qu'un montant de 32'572 fr. d'actes de défaut de biens. Il a par ailleurs bénéficié de l'aide sociale à partir d'août 2010. Finalement, il convient encore de relever un dernier point déterminant excluant toute intégration suffisante. Le recourant, par son comportement délictuel ayant conduit à 17 condamnations, dont une à 30 mois de peine privative de liberté pour diverses infractions à la LStup, a en effet clairement démontré une propension à ne pas se conformer à l'ordre juridique.
Les arguments du recourant ne permettent pas d'arriver à une autre conclusion. Outre qu'il affirme ne pas dépendre de l'aide sociale, ce qui est contraire aux faits retenus par l'autorité précédente liant le Tribunal fédéral (<ref-law>), le simple fait qu'il ait la volonté de retrouver un travail et qu'il considère le montant de ses poursuites comme peu élevé, compte tenu de la durée de sa présence en Suisse, ne sont pas des éléments suffisants pour remettre en cause l'appréciation du Tribunal administratif fédéral, en particulier sur le vu de son incapacité crasse à se conformer au système juridique suisse. Les remarques qu'il fait en relation avec ses condamnations sont sans pertinence, le recourant ayant, contrairement à ce qu'il affirme, continué ses activités délictuelles malgré son mariage et la naissance de son enfant. Dans ces conditions, c'est sans violer le droit fédéral que le Tribunal administratif fédéral a nié l'existence d'une intégration suffisante. Il n'est par conséquent pas nécessaire d'examiner la durée de l'union conjugale, ces deux conditions étant cumulatives (cf. <ref-ruling> consid. 3.5.3 p. 295).
5.
5.1. Selon l'art. 50 al. 1 let. b LEI, après dissolution de la famille, le droit du conjoint et des enfants à l'octroi d'une autorisation de séjour et à la prolongation de sa durée de validité en vertu des art. 42 et 43 LEI subsiste lorsque la poursuite du séjour du recourant en Suisse s'impose pour des raisons personnelles majeures. De telles raisons peuvent en particulier découler d'une relation digne de protection avec un enfant qui a le droit de séjourner en Suisse (cf. <ref-ruling> consid. 2.1 p. 319). Dans ce cas, les conditions posées par l'art. 50 al. 1 let. b LEI ne recoupent pas nécessairement celles de l'octroi d'un titre de séjour fondé sur l'art. 8 CEDH. Le droit au respect de la vie familiale garantie par les art. 8 CEDH et 13 Cst. doit néanmoins être pris en compte dans l'application de l'art. 50 al. 1 let. b LEI dont l'application ne saurait être plus restrictive que celle des art. 8 CEDH et 13 Cst. (arrêt 2C_652/2013 du 17 décembre 2013 consid. 2.3 et les références, non publié in <ref-ruling>). L'art. 17 du Pacte international du 16 décembre 1966 relatif aux droits civils et politiques (ci-après: le Pacte ONU II; RS 0.103.2) n'offre pas non plus une protection plus étendue que l'art. 8 CEDH sous cet angle (cf. <ref-ruling> consid. 7.1 p. 421 s.).
5.2. L'art. 8 CEDH ne confère en principe pas un droit à séjourner dans un Etat déterminé. Le fait de refuser un droit de séjour à un étranger dont la famille se trouve en Suisse peut toutefois entraver sa vie familiale et porter ainsi atteinte au droit au respect de la vie privée et familiale garanti par cette disposition. Il n'y a cependant pas atteinte à la vie familiale si l'on peut attendre des membres de la famille qu'ils réalisent leur vie de famille à l'étranger; l'art. 8 CEDH n'est a priori pas violé si le membre de la famille jouissant d'un droit de présence en Suisse peut quitter ce pays sans difficultés avec l'étranger auquel a été refusée une autorisation de séjour. En revanche, si le départ du membre de la famille pouvant rester en Suisse ne peut d'emblée être exigé sans autres difficultés, il convient de procéder à la pesée des intérêts prévue par l'art. 8 par. 2 CEDH. Celle-ci suppose de tenir compte de l'ensemble des circonstances et de mettre en balance l'intérêt privé à l'obtention d'un titre de séjour et l'intérêt public à son refus (<ref-ruling> consid. 4.2 p. 96 et les références).
5.3. Dans un arrêt récent (<ref-ruling>), le Tribunal fédéral a rappelé la jurisprudence relative à l'application de l'art. 8 CEDH pour le parent étranger qui n'a pas l'autorité parentale ni la garde d'un enfant mineur disposant d'un droit durable de résider en Suisse. Il a en outre rappelé que cette jurisprudence s'appliquait également lorsque les parents sont titulaires de l'autorité parentale conjointe, ce qui est généralement la règle depuis l'entrée en vigueur des modifications du Code civil le 1 er juillet 2014 [cf. RO 2014 357]; cf. <ref-ruling> consid. 3 p. 62 s.), mais que seul l'un des deux a la garde de l'enfant (cf. <ref-ruling> consid. 5.5.4 p. 32). Le parent qui n'a pas la garde ne peut d'emblée entretenir une relation familiale avec son enfant que de manière limitée, en exerçant le droit de visite dont il bénéficie. Il n'est en principe pas nécessaire que, dans l'optique de pouvoir exercer son droit de visite, il soit habilité à résider durablement dans le même pays que son enfant. Sous l'angle du droit à une vie familiale (cf. art. 8 par. 1 CEDH et 13 al. 1 Cst.), il suffit en règle générale que le parent vivant à l'étranger exerce son droit de visite dans le cadre de séjours brefs, au besoin en aménageant ses modalités quant à la fréquence et à la durée ou par le biais de moyens de communication modernes. Le droit de visite d'un parent sur son enfant ne doit en effet pas nécessairement s'exercer à un rythme bimensuel et peut également être organisé de manière à être compatible avec des séjours dans des pays différents (<ref-ruling> consid. 5.1 p. 96 s. et les références).
Selon la jurisprudence constante du Tribunal fédéral (<ref-ruling> consid. 5.2 p. 97 et les références), un droit plus étendu ne peut le cas échéant exister qu'en présence 1) de relations étroites et effectives avec l'enfant d'un point de vue affectif et 2) d'un point de vue économique, 3) de l'impossibilité pratique à maintenir la relation en raison de la distance qui sépare le pays de résidence de l'enfant du pays d'origine de son parent et 4) d'un comportement irréprochable. Ces exigences doivent être appréciées ensemble et faire l'objet d'une pesée des intérêts globale. Dans le cadre de l'examen de la proportionnalité de la mesure (cf. art. 8 par. 2 CEDH), il faut aussi tenir compte de l'intérêt fondamental de l'enfant (art. 3 de la Convention relative aux droits de l'enfant [CDE; RS 0.107]) à pouvoir grandir en jouissant d'un contact étroit avec ses deux parents, étant précisé que, sous l'angle du droit des étrangers, cet élément n'est pas prépondérant par rapport aux autres et que l'art. 3 CDE ne saurait fonder une prétention directe à l'octroi ou au maintien d'une autorisation (<ref-ruling> consid. 5.2 p. 98 et les références).
5.4. Dans l'arrêt entrepris, le Tribunal administratif fédéral a laissé la question des relations affectives avec l'enfant ouverte, faute d'éléments probants suffisants à sa disposition, notamment en raison d'une collaboration relativement mauvaise de la part du recourant quant à la détermination des faits pertinents. Il a en revanche admis l'existence de relations économiques entre le recourant et son fils, ce qu'il est possible de confirmer, compte tenu du versement régulier des contributions dues en faveur de celui-ci. L'autorité précédente a cependant nié l'existence d'un comportement irréprochable.
5.4.1. On ne saurait parler de comportement irréprochable lorsqu'il existe, à l'encontre de l'étranger, des motifs d'éloignement, en particulier si l'on peut lui reprocher un comportement répréhensible sur le plan pénal ou en regard de la législation sur les étrangers, étant entendu qu'en droit des étrangers, le respect de l'ordre et de la sécurité publics ne se recoupent pas nécessairement avec la violation de dispositions pénales, de sorte que l'appréciation émise par l'autorité de police des étrangers peut s'avérer plus rigoureuse que celle de l'autorité pénale. La jurisprudence a toutefois relativisé cette condition dans des situations spécifiques. Ainsi, lorsque l'éloignement du parent étranger qui a la garde exclusive et l'autorité parentale remettrait en cause le séjour de l'enfant de nationalité suisse en Suisse, la jurisprudence n'exige plus du parent qui entend se prévaloir de l'art. 8 CEDH un comportement irréprochable et seule une atteinte d'une certaine gravité à l'ordre et à la sécurité publics peut l'emporter sur le droit de l'enfant à pouvoir grandir en Suisse. Par ailleurs, en présence d'une atteinte de peu d'importance à l'ordre public et d'un lien affectif et économique particulièrement fort avec l'enfant, la contrariété à l'ordre public ne constitue plus une condition indépendante rédhibitoire de refus de prolongation de l'autorisation de séjour, mais un élément parmi d'autres à prendre en compte dans la pesée globale des intérêts (<ref-ruling> consid. 5.2.4 p. 100 et les références).
5.4.2. En tout premier lieu, contrairement à ce que semble penser le recourant, il ne ressort pas des faits retenus qu'il bénéficierait de la garde exclusive sur son enfant de nationalité suisse. Au contraire, il en ressort clairement que c'est la mère de cet enfant qui en bénéficie. Dans ce cas de figure, il ne saurait être question d'appliquer au recourant la jurisprudence visant à éviter de remettre en cause le séjour de l'enfant de nationalité suisse en Suisse. Ensuite, comme on l'a vu précédemment, le recourant, durant ses années de présence en Suisse, n'a cessé d'occuper les autorités pénales. Il a en effet été condamné à 17 reprises. Si toutes les condamnations n'ont pas été prononcées pour des faits d'une importante gravité, il faut malgré tout relever que le recourant a été condamné à 30 mois de peine privative de liberté pour des infractions à la LStup, c'est-à-dire des infractions envers lesquelles le Tribunal fédéral se montre particulièrement rigoureux (<ref-ruling> consid. 5.3 p. 126 et les références). En outre, la répétition de ces infractions, même si certaines n'ont été sanctionnées "que" par des amendes, démontre l'incapacité du recourant à respecter l'ordre juridique et l'absence de prise de conscience dont il fait preuve. A cela s'ajoute le fait que le recourant, durant sa présence en Suisse a accumulé de nombreuses dettes, se trouvant ainsi aux poursuites pour plusieurs milliers de francs et émargeant à l'aide sociale. Tous ces éléments, pris dans leur ensemble, excluent de retenir un comportement irréprochable de la part du recourant.
5.5. Aux éléments qui précèdent et qui ont trait au comportement du recourant, il convient encore d'ajouter que, si le recourant se trouve depuis 2005 en Suisse, il y a passé une grande partie dans l'illégalité et a à plusieurs reprises refusé de se conformer aux décisions de renvoi ordonnées à son encontre. Par ailleurs, ni son mariage, ni la naissance de son enfant n'ont empêché le recourant de maintenir une fréquence élevée d'infractions, celui-ci ayant été condamné à neuf reprises après la naissance de son fils, respectivement sept reprises après son mariage. Il est donc malvenu d'affirmer que la naissance de son fils l'a fait changer drastiquement de comportement. De plus, déjà lors du mariage et de la conception de l'enfant, les époux ne pouvaient ignorer que la situation du recourant en Suisse était précaire. Finalement, même si un retour en Algérie ne sera probablement pas aisé pour le recourant, celui-ci y a cependant vécu durant la majeure partie de sa vie et en parle encore la langue, ce qui facilitera sa réintégration. Il pourra en outre compter sur les membres de sa famille qui s'y trouvent et profiter des expériences professionnelles acquises en Suisse. L'intérêt public à l'éloignement du recourant de Suisse l'emporte donc sur celui de ce dernier à rester dans ce pays pour exercer son droit de visite. Il lui appartiendra d'aménager d'autres moyens pour exercer ce droit et maintenir des contacts avec son fils, comme par exemple accueillir cet enfant dans son pays d'origine lors de vacances ou le contacter par téléphone ou Internet.
6.
Sur le vu des considérants qui précèdent, le recours en matière de droit public est rejeté. Succombant, le recourant doit supporter les frais judiciaires (<ref-law>). Il n'est pas alloué de dépens (art. 68 al. 1 et 3 LTF).

Par ces motifs, le Tribunal fédéral prononce :
1.
Le recours en matière de droit public est rejeté.
2.
Le recours constitutionnel subsidiaire est irrecevable.
3.
Les frais judiciaires, arrêtés à 2'000 fr., sont mis à la charge du recourant.
4.
Le présent arrêt est communiqué au mandataire du recourant, au Secrétariat d'Etat aux migrations, à la Cour VI du Tribunal administratif fédéral et au Service des migrations de la République et canton de Neuchâtel.
Lausanne, le 23 avril 2019
Au nom de la IIe Cour de droit public
du Tribunal fédéral suisse
Le Président : Seiler
Le Greffier : Tissot-Daguette