Faits :
A.
A.a. A._, ressortissant algérien né en 1981, est arrivé illégalement en Suisse en 2002. Le 16 février 2007, il a épousé B._, ressortissante tunisienne née en 1982 alors au bénéfice d'une autorisation de séjour annuelle. Trois enfants sont issus de cette union: C._, née en 2007, D._, née en 2008 et E._, né en 2010. Ceux-ci, de même que leur mère, ont obtenu des autorisations d'établissement le 4 novembre 2010. A._ et B._ se sont séparés en septembre 2013. Leur divorce a été prononcé le 11 juin 2014.
A.b. L'Office fédéral de l'immigration, de l'intégration et de l'émigration (actuel Secrétariat d'Etat aux migrations) a, par décision du 18 novembre 2004, interdit à A._ d'entrer en Suisse pour une durée de dix ans. Cette décision est entrée en force. Il en a été de même de la décision du 16 novembre 2007 du Service de la population du canton de Vaud (ci-après: le Service cantonal) refusant de délivrer une autorisation de séjour par regroupement familial à A._, ainsi que de la décision de cette même autorité du 11 août 2008 rejetant la demande de réexamen déposée par l'intéressé le 17 juin 2008. Au terme d'une procédure consécutive à la nouvelle demande de réexamen formulée par A._ le 12 janvier 2009, le Tribunal administratif fédéral a, par arrêt du 6 mars 2012, approuvé l'octroi d'une autorisation de séjour au titre de regroupement familial en faveur de l'intéressé et levé avec effet immédiat la décision d'interdiction d'entrée du 18 novembre 2004. Cette autorité a en outre attiré l'attention de A._ sur le fait qu'il devrait à l'avenir s'abstenir de commettre toute infraction, à défaut de quoi les autorités compétentes seraient probablement amenées, après réexamen de sa situation, à prononcer des mesures à son encontre. Le Service cantonal avait déjà informé le recourant en ce sens le 12 mars 2010. Le 19 mars 2012, A._ s'est vu délivrer une autorisation de séjour par regroupement familial, régulièrement prolongée jusqu'au 15 février 2015.
A.c. Durant son séjour en Suisse, A._ a été condamné pénalement à treize reprises dont cinq pour des faits commis après la délivrance de son autorisation de séjour :
- le 2 août 2002, par le Juge d'instruction de l'arrondissement de Lausanne, à une peine de 151 jours d'emprisonnement, assortie d'un sursis de deux ans, pour vol, délit manqué d'utilisation frauduleuse d'un ordinateur et infraction à l'ancienne loi fédérale du 26 mars 1931 sur le séjour et l'établissement des étrangers (LSEE; RO 49 279); l'expulsion du territoire suisse a en outre été prononcée pour trois ans;
- le 30 septembre 2004, par le Juge d'instruction de l'arrondissement de Lausanne, à une peine de deux mois d'emprisonnement partiellement complémentaire à celle prononcée le 2 août 2002, le sursis accordé alors étant révoqué, pour vol, vol d'importance mineure, tentative de vol, contravention à la loi fédérale sur les stupéfiants et les substances psychotropes (LStup; RS 812.121) et infraction à la LSEE; l'expulsion ferme du territoire suisse a en outre été prononcée pour une durée de trois ans;
- le 15 février 2005, par le Juge d'instruction de l'arrondissement de l'Est vaudois, à une peine d'emprisonnement de 100 jours, pour vol et rupture de ban;
- le 2 juin 2006, par le Juge d'instruction de l'arrondissement de Lausanne, à une peine de six mois d'emprisonnement, pour vol, recel, rupture de ban et contravention à la LStup;
- le 23 août 2006, par le Juge d'instruction de l'arrondissement de Lausanne, à une peine de deux mois d'emprisonnement pour rupture de ban;
- le 3 novembre 2008, par le Tribunal de police de l'arrondissement de Lausanne, à une peine pécuniaire de 180 jours-amende et à une amende de 500 fr. pour contravention et infraction à la LSEE et pour infraction à la loi fédérale du 16 décembre 2005 sur les étrangers (LEtr; RS 142.20);
- le 17 décembre 2009, par le Juge d'instruction de l'arrondissement de Lausanne, à une peine de 120 jours-amende pour infraction à la LEtr;
- le 11 juillet 2012, par le Tribunal de police de l'arrondissement de l'Est vaudois, à 200 heures de travail d'intérêt général pour infraction à la LEtr (infraction commise du 17 décembre 2009 au 5 avril 2011);
- le 4 septembre 2013, par le Ministère public du canton de Vaud, à une peine privative de liberté de 30 jours pour vol (infraction commise le 3 septembre 2013);
- le 30 avril 2014, par le Tribunal de police de l'arrondissement de l'Est vaudois, à une peine privative de liberté de 60 jours pour recel (infraction commise le 5 janvier 2014);
- le 4 décembre 2014, par le Ministère public de l'arrondissement de l'Est vaudois, à une peine privative de liberté de 90 jours partiellement complémentaire à celle prononcée le 30 avril 2014, pour vol, dommages à la propriété et violation de domicile (infractions commises les 6 octobre 2013, 8 mars et 7 mai 2014);
- le 4 mai 2015, par le Ministère public de l'arrondissement de l'Est vaudois, à une peine privative de liberté de 180 jours et à une amende de 400 fr. pour divers vols, infraction à la loi fédérale du 20 juin 1997 sur les armes, les accessoires d'armes et les munitions (LArm; RS 514.54) et contravention à la LStup (infractions commises les 20, 24 et 26 décembre 2014, 3 janvier, ainsi que les 1er, 9 et 10 mars 2015);
- le 7 juillet 2016, par le Ministère public de l'arrondissement de l'Est vaudois, à une peine de 20 jours-amende pour avoir, comme titulaire d'un permis d'élève conducteur, circulé au volant d'un véhicule automobile sans être réglementairement accompagné (infraction commise le 3 juin 2016).
A.d. A._ s'est trouvé en incapacité de travail du 20 juillet 2012 au 30 septembre 2016. Il bénéficie du revenu d'insertion depuis le 1er septembre 2013, le montant perçu à ce titre s'élevant 52'183 fr. 45 au 14 août 2015.
B.
Par décision du 25 février 2016, le Service cantonal a refusé de prolonger l'autorisation de séjour de A._ et a prononcé son renvoi de Suisse. La Cour de droit administratif et public du Tribunal cantonal du canton de Vaud (ci-après : le Tribunal cantonal) a rejeté le recours interjeté par l'intéressé contre cette décision par arrêt du 12 janvier 2017.
C.
Agissant par la voie du recours en matière de droit public au Tribunal fédéral, A._ conclut, sous suite de frais et dépens, outre l'effet suspen sif, principalement à l'annulation de l'arrêt du Tribunal cantonal du 12 janvier 2017 et à la prolongation de son autorisation de séjour, subsidiairement au renvoi de la cause à l'autorité précédente pour nouvelle décision au sens des considérants.
Par ordonnance du 15 février 2017, le Président de la IIe Cour de droit public du Tribunal fédéral a accordé l'effet suspensif au recours.
Le Tribunal cantonal conclut au rejet du recours. Le Service cantonal renonce à se déterminer. Le recourant n'a pas déposé d'observations finales. Le 3 mai 2017, le Service cantonal a déposé une nouvelle pièce.

Considérant en droit :
1.
Le Tribunal fédéral examine d'office et avec une pleine cognition la recevabilité des recours qui lui sont soumis (<ref-ruling> consid. 1.1 p. 197; <ref-ruling> consid. 2.1 p. 397).
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; <ref-ruling> consid. 1.1 p. 179).
Pour fonder son droit à une autorisation de séjour, le recourant se prévaut de raisons personnelles majeures au sens de l'art. 50 al. 1 let. b LEtr ainsi que du droit au respect de la vie familiale garanti à l'art. 8 par. 1 CEDH et 13 al. 1 Cst. La relation étroite et effective qu'il dit entretenir avec ses trois enfants titulaires d'une autorisation d'établissement et qui vivent auprès de leur mère étant potentiellement de nature à lui conférer un droit à l'obtention d'une prolongation de son autorisation de séjour, son recours échappe au motif d'irrecevabilité prévu à l'art. 83 let. c ch. 2 LTF.
1.2. Pour le surplus, l'arrêt attaqué est une décision finale (art. 90 LTF) rendue par une autorité cantonale supérieure de dernière instance (art. 86 al. 1 let. d et 2 LTF) dans une cause de droit public (art. 82 let. a LTF). Déposé en temps utile (art. 100 al. 1 LTF) et dans les formes prescrites (art. 42 LTF), par le destinataire de l'arrêt entrepris qui a qualité pour recourir (cf. art. 89 al. 1 LTF), le recours est partant recevable.
1.3. Aucun fait nouveau ni preuve nouvelle ne peut être présenté à moins de résulter de la décision de l'autorité précédente (art. 99 al. 1 LTF). Il appartient, le cas échéant, aux parties d'exposer les raisons pour lesquelles elles considèrent être en droit de présenter exceptionnellement des faits ou des moyens de preuve nouveaux (cf. <ref-ruling> consid. 3 p. 395; arrêts 2C_1002/2015 du 14 septembre 2016 consid. 1.2; 8C_805/2015 du 10 juin 2016 consid. 3). En l'occurrence, la pièce nouvelle produite par le Service cantonal le 3 mai 2017 est irrecevable.
2.
Le recourant se plaint de la constatation manifestement inexacte des faits.
2.1. Saisi d'un recours en matière de droit public, le Tribunal fédéral examine librement la violation du droit fédéral (cf. art. 95 let. a et 106 al. 1 LTF). Il statue sur la base des faits établis par l'autorité précédente (art. 105 al. 1 LTF), sous réserve des cas prévus à l'art. 105 al. 2 LTF. La partie recourante 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'art. 95 LTF ou de manière manifestement inexacte, c'est-à-dire arbitraire (<ref-ruling> consid. 1.4.1 p. 100), et si la correction du vice est susceptible d'influer sur le sort de la cause (art. 97 al. 1 LTF; <ref-ruling> consid. 6 p. 358; <ref-ruling> consid. 4.2 p. 233 s.). Conformément à l'art. 106 al. 2 LTF, la partie recourante doit expliquer de manière circonstanciée en quoi ces conditions seraient réalisées. Les faits et les critiques invoqués de manière appellatoire sont irrecevables (<ref-ruling> consid. 2.4 p. 368; <ref-ruling> consid. 2.3 p. 266).
2.2. Le recourant estime que, compte tenu du certificat médical du 30 août 2016 attestant de son incapacité de travail totale pour la période allant du 20 juillet 2012 au 30 septembre 2016, le Tribunal cantonal aurait dû retenir que sa dépendance à l'aide sociale d'une part et l'absence de versements, par ses soins, de pensions alimentaires en faveur de ses enfants d'autre part ne lui étaient pas imputables. En réalité, l'argumentation de l'intéressé ne porte pas sur l'établissement des faits mais sur l'appréciation juridique de son incapacité de travail. Or, il s'agit là d'une question de droit que le Tribunal fédéral examinera ci-après (cf. infra consid. 3.6 et 4).
2.3. Il ressort de l'arrêt entrepris que le recourant et son épouse se sont séparés en septembre 2013 et que leur divorce a été prononcé le 11 juin 2014. Le grief du recourant selon lequel le Tribunal cantonal n'aurait pas fait mention de ces éléments de fait tombe dès lors à faux.
2.4. Le recourant fait valoir que l'autorité précédente aurait dû indiquer qu'il avait exercé une activité professionnelle depuis 2008 et ce jusqu'à ce que les autorités cantonales lui eussent, à une date indéterminée mais antérieure à l'arrêt du Tribunal administratif fédéral du 6 mars 2012, formellement interdit de travailler. En l'occurrence, les éléments avancés par le recourant, à supposer qu'ils aient été effectivement écartés de manière arbitraire par le Tribunal cantonal - question qui peut demeurer indécise -, ne sont de toute façon pas propres à modifier la décision attaquée. Comme on le verra ci-dessous (cf. infra consid. 3.6, 3.7 et 4), l'éventuel complément de l'état de fait dans le sens requis par l'intéressé ne justifierait en effet pas de trancher différemment la question du droit au regroupement familial de ce dernier. Le grief du recourant doit donc être écarté.
2.5. Au surplus, dans la mesure où le recourant présente une argumentation partiellement appellatoire, en opposant sa propre version des faits à celle du Tribunal cantonal, sans cependant invoquer ni l'arbitraire, ni une constatation manifestement inexacte des faits, le Tribunal fédéral ne peut pas en tenir compte. Il statuera donc sur la base des faits tels qu'ils ressortent de l'arrêt attaqué.
3.
Le recourant invoque une violation des art. 50 al. 1 let. b LEtr, 8 CEDH, 13 Cst., ainsi que 3 par. 1 et 9 par. 3 de la Convention du 20 novembre 1989 relative aux droits de l'enfant (CDE; RS 0.107).
3.1. Selon l'art. 50 al. 1 let. b 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 art. 42 et 43 LEtr subsiste lorsque la poursuite du séjour 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 (<ref-ruling> consid. 4.1 p. 24; <ref-ruling> consid. 2.1 p. 318 s.). Il convient alors d'apprécier la situation dans son ensemble et d'appliquer la loi de manière conforme au droit constitutionnel (cf. art. 13 al. 1 Cst.) et conventionnel (<ref-ruling> consid. 4.1 p. 24 s.; arrêts 2C_1050/2016 du 10 mars 2017 consid. 5.1; 2C_1125/2014 du 9 septembre 2015 consid. 4.1 et les références). Les prétentions découlant de l'art. 50 al. 1 let. b LEtr ne sont, dans les limites de son champ d'application, en principe pas moins étendues que celles découlant des art. 13 al. 1 Cst. et 8 CEDH et se recoupent partiellement avec ces dernières (<ref-ruling> consid. 4.1 p. 25 et les arrêts cités; arrêt 2C_1050/2016 du 10 mars 2017 consid. 5.1).
3.2. Un étranger peut se prévaloir de l'art. 8 par. 1 CEDH (et de l'art. 13 Cst.), qui garantit le droit au respect de la vie privée et familiale, pour s'opposer à l'éventuelle séparation de sa famille pour autant qu'il entretienne une relation étroite et effective avec une personne de sa famille ayant le droit de résider durablement en Suisse (<ref-ruling> consid. 2.1 p. 335 s.; <ref-ruling> consid. 1.3.1 p. 145 s.; <ref-ruling> consid. 3.1 p. 286).
Le droit au respect de la vie privée et familiale garanti par l'art. 8 par. 1 CEDH n'est toutefois pas absolu. Une ingérence dans l'exercice de ce droit est possible selon l'art. 8 par. 2 CEDH, pour autant qu'elle soit prévue par la loi et qu'elle constitue une mesure qui, dans une société démocratique, est nécessaire à la sécurité nationale, à la sûreté publique, au bien-être économique du pays, à la défense de l'ordre et à la prévention des infractions pénales, à la protection de la santé ou de la morale ou à la protection des droits et libertés d'autrui. La mise en oeuvre d'une politique restrictive en matière de séjour des étrangers constitue un but légitime au regard de cette disposition conventionnelle (<ref-ruling> consid. 2.1 p. 288; <ref-ruling> consid. 2.2.1 p. 156).
Le refus d'octroyer une autorisation de séjour (ou d'établissement) fondé sur l'art. 8 par. 2 CEDH ne se justifie que si la pesée des intérêts à effectuer dans le cas d'espèce fait apparaître la mesure comme proportionnée aux circonstances (<ref-ruling> consid. 2.2 p. 147 s.; <ref-ruling> consid. 4.3 p. 381). Cette condition correspond aux exigences de l'art. 96 LEtr (<ref-ruling> consid. 2.1 p. 287 s.). Lors de l'examen de la proportionnalité, il y a lieu de prendre en considération la gravité de l'éventuelle faute commise par l'étranger, la durée de son séjour en Suisse, son degré d'intégration, ainsi que le préjudice qu'il aurait à subir avec sa famille du fait de l'expulsion, respectivement du refus d'accorder ou de prolonger une autorisation de séjour (<ref-ruling> consid. 2.3 p. 148 s.; <ref-ruling> consid. 4.3 et 4.4 p. 381 s.; <ref-ruling> consid. 4.1 p. 185).
3.3. Le parent qui n'a pas l'autorité parentale ni la garde de l'enfant ne peut d'emblée entretenir une relation familiale avec celui-ci que de manière limitée, en exerçant le droit de visite dont il bénéficie. Or, il n'est en principe pas nécessaire que, dans l'optique de pouvoir exercer son droit de visite, le parent étranger 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 art. 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 de courte durée, au besoin en aménageant ses modalités quant à la fréquence et à la durée, ou en recourant aux moyens de communication traditionnels et modernes transfrontaliers (cf. <ref-ruling> consid. 5.3 p. 28; <ref-ruling> consid. 2.2 p. 319; arrêt 2C_1050/2016 du 10 mars 2017 consid. 6.2). 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 (cf. <ref-ruling> consid. 3.2 p. 147). Selon la jurisprudence constante du Tribunal fédéral, un droit plus étendu ne peut le cas échéant exister qu'en présence de liens familiaux particulièrement forts d'un point de vue affectif et économique, lorsque cette relation ne pourrait pratiquement pas être maintenue en raison de la distance qui sépare le pays de résidence de l'enfant du pays d'origine de son parent, et que l'étranger a fait preuve en Suisse d'un comportement irréprochable (<ref-ruling> consid. 5.2 p. 27; <ref-ruling> consid. 6.2 p. 47; <ref-ruling> consid. 3.2 p. 147; <ref-ruling> consid. 2.2 p. 319; arrêt 2C_1050/2016 du 10 mars 2017 consid. 6.1). Ces exigences doivent être appréciées ensemble et faire l'objet d'une pesée des intérêts globale (arrêts 2C_1066/2016 du 31 mars 2017 consid. 4.2; 2C_520/2016 du 13 janvier 2017 consid. 4.2 et les arrêts cités). Dans le cadre de l'examen de la proportionnalité de la mesure (cf. art. 8 par. 2 CEDH, art. 96 LEtr et art. 13 cum art. 36 Cst.), il faut aussi tenir compte de l'intérêt fondamental de l'enfant (art. 3 CDE) à pouvoir grandir en jouissant d'un contact étroit avec ses deux parents (<ref-ruling> consid. 5.5.1 p. 29; arrêts 2C_1050/2016 du 10 mars 2017 consid. 5.1; 2C_520/2016 du 13 janvier 2017 consid. 4.2 et les arrêts cités; cf. aussi arrêt de la CourEDH El Ghatet c. Suisse du 8 novembre 2016 [requête n o 56971/10], par. 27 s. et 46 s.), étant précisé que, sous l'angle du droit des étrangers, cet élément n'est pas prépondérant par rapport aux autres (cf. <ref-ruling> consid. 5.5.1 p. 29 s.; <ref-ruling> consid. 2.4 p. 321; arrêts 2C_1050/2016 du 10 mars 2017 consid. 5.1; 2C_997/2015 du 30 juin 2016 consid. 4.3; 2C_497/2014 du 26 octobre 2015 consid. 5.1) et que l'art. 3 CDE qui le protège ne saurait fonder une prétention directe à l'octroi ou au maintien d'une autorisation (<ref-ruling> consid. 3.2 p. 148; <ref-ruling> consid. 2.4 s. p. 320 s.; arrêts 2C_1050/2016 du 10 mars 2017 consid. 5.1; 2C_165/2016 du 8 septembre 2016 consid. 5.3).
3.4. L'exigence du lien affectif particulièrement fort doit être considérée comme remplie lorsque les contacts personnels sont effectivement exercés dans le cadre d'un droit de visite usuel selon les standards d'aujourd'hui (en Suisse romande, il s'agit d'un droit de visite d'un week-end toutes les deux semaines et durant la moitié des vacances; cf. ATF <ref-ruling> consid. 2.5 p. 321 s.; cf. aussi <ref-ruling> consid. 3.2 p. 148; arrêts 2C_520/2016 du 13 janvier 2017 consid. 4.3; 2C_420/2015 du 1 er octobre 2015 consid. 2.3; 2C_794/2014 du 23 janvier 2015 consid. 3.2).
3.5. Selon la jurisprudence, 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 (arrêts 2C_1066/2016 du 31 mars 2017 consid. 4.4; 2C_60/2016 du 25 mai 2016 consid. 4.2.3; 2C_762/2013 du 31 janvier 2014 consid. 5.1 in fine). Par ailleurs, 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 (<ref-ruling> consid. 4.3 p. 150 s.; 2C_1066/2016 du 31 mars 2017 consid. 4.4).
3.6. En l'occurrence, il ressort des constatations de l'autorité précédente, qui lient le Tribunal de céans (cf. art. 105 al. 1 LTF), que le recourant jouit de l'autorité parentale conjointe sur ses enfants, qui ont le droit de résider durablement en Suisse. Il n'est pas contesté qu'il entretient un lien affectif particulièrement fort avec ceux-ci, les contacts personnels correspondant à un droit de visite usuel selon les standards d'aujourd'hui. Il s'agit donc uniquement de déterminer si les liens familiaux sont particulièrement forts d'un point de vue économique. Le divorce a été prononcé le 11 juin 2014..Selon l'arrêt entrepris, il résulte de la convention réglant les effets accessoires du divorce que le recourant n'est pas astreint au versement d'une contribution d'entretien, tant qu'il ne couvre pas son minimum vital. Le recourant ne contribue ainsi pas à l'entretien de ses enfants et ne prétend pas avoir été en mesure de le faire depuis la séparation d'avec son épouse. Il explique que cela est dû à son incapacité de travail totale, qui s'est étendue du 20 juillet 2012 au 30 septembre 2016. Il faut toutefois constater que celle-ci ne l'a pas empêché de commettre des infractions avec une certaine régularité - notamment des vols, des dommages à la propriété et une violation de domicile -, de sorte qu'elle peut être relativisée. A cela s'ajoute que le recourant a continué de bénéficier de l'aide sociale après que son incapacité de travail totale a pris fin. Or, la séparation de son couple en septembre 2013 et ses obligations d'entretien auraient dû le conduire à chercher activement un emploi lui permettant à la fois d'être autonome financièrement et de verser des pensions alimentaires. Le recourant ne soutient pas que tel aurait été le cas. Dans ces conditions, il ne saurait être considéré que le recourant a la volonté de subvenir aux besoins de ses enfants. L'arrêt du Tribunal cantonal doit donc être confirmé en tant qu'il constate l'absence de lien économique fort entre le recourant et ses trois enfants. Une éventuelle contribution du recourant à l'entretien de sa famille, antérieurement à la délivrance de son autorisation de séjour, ne saurait modifier cette conclusion, dès lors que ce sont les rapports existants et effectivement vécus au moment où l'autorité judiciaire précédant le Tribunal fédéral rend sa décision qui sont déterminants (arrêts 2C_1050/2016 du 10 mars 2017 consid. 6.2; 2C_1031/2011 du 22 mars 2012 consid. 4.1.4 avec les références).
3.7. De plus, le recourant, qui a été condamné à treize reprises depuis qu'il est en Suisse et continue de dépendre de l'aide sociale bien qu'il ait recouvré sa capacité de travailler à compter du 1 er octobre 2016, ne saurait se targuer d'un comportement irréprochable, ce d'autant moins qu'il ne se trouve pas dans l'une des situations pour lesquelles la jurisprudence en la matière a été assouplie (cf. <ref-ruling> consid. 4.1 p. 148 s.; arrêts 2C_520/2016 du 13 janvier 2017 consid. 4.5; 2C_723/2014 du 6 août 2015 consid. 2.3; 2C_165/2014 du 18 juillet 2014 consid. 4.3; 2C_606/2013 du 4 avril 2014 consid. 5.3).
3.8. Ces circonstances, prises dans leur ensemble, à savoir l'absence de relations économiques particulièrement fortes entre le recourant et ses enfants, ainsi que le comportement en Suisse de l'intéressé, font apparaître que les précédents juges n'ont pas violé les art. 50 al. 1 let. b LEtr, 8 CEDH, 3 par. 1 et 9 par. 3 CDE en considérant que la relation familiale existant entre le recourant et ses enfants ne constituait pas une raison personnelle majeure imposant la poursuite du séjour du recourant dans ce pays.
4.
En dernier lieu, hormis les liens du recourant avec ses enfants, dont on a vu que, bien qu'il soit dans l'intérêt de ceux-ci de pouvoir grandir en jouissant d'un contact étroit avec les deux parents, ils ne justifient pas à eux seuls son séjour en Suisse, l'arrêt attaqué ne révèle aucun élément déterminant qui ferait apparaître le refus d'approuver la prolongation de l'autorisation de séjour de l'intéressé comme disproportionné (cf. art. 96 LEtr). Le recourant se trouve certes en Suisse depuis quelque quinze ans. Il a néanmoins séjourné en Suisse illégalement ou au bénéfice de l'effet suspensif durant une dizaine d'années. Celles-ci ne sauraient dès lors être prises en considération (cf. <ref-ruling> consid. 4.4 p. 14). Le recourant n'a par ailleurs jamais travaillé en Suisse depuis l'obtention de son autorisation de séjour en 2012, de sorte que, depuis environ cinq ans, il n'est pas intégré professionnellement, peu importe qu'il ait éventuellement exercé une activité lucrative lui permettant de subvenir à ses besoins auparavant. Le recourant dépend par ailleurs de l'aide sociale depuis quelque quatre ans. Il explique celle-ci par son incapacité de travail totale, qui s'est étendue du 20 juillet 2012 au 30 septembre 2016. Pour les motifs déjà évoqués, celle-ci doit toutefois être relativisée (cf. supra consid. 3.6). A cela s'ajoute que le recourant a continué de bénéficier de l'aide sociale après que son incapacité de travail totale a pris fin. Il ne ressort pas du dossier que le recourant se serait efforcé depuis lors de trouver un emploi lui permettant de s'assumer financièrement. Il ne le soutient d'ailleurs pas. Dans ces circonstances, le recourant ne saurait être totalement exempté de responsabilité s'agissant de sa dépendance à l'aide sociale. Quant aux conditions de réintégration du recourant dans son pays d'origine, il ressort de l'arrêt attaqué que l'intéressé a passé en Algérie son enfance, son adolescence et les premières années de sa vie d'adulte, soit jusqu'à 20 ans. On peut donc présumer qu'il y conserve des attaches culturelles, sociales et également familiales, puisque celui-ci - qui se limite à alléguer que ses chances de réintégration seraient "maigres" sans fournir plus de détails - ne prétend pas le contraire. Le recourant a par ailleurs recouvré un état de santé qui lui permet de travailler. Son éloignement ne l'empêchera de surcroît pas d'entretenir des contacts avec ses enfants et de contribuer financièrement à leur entretien. Cela étant, même si son retour en Algérie exigera du recourant un certain effort d'adaptation, une réintégration ne paraît pas d'emblée insurmontable, étant précisé que le simple fait que l'étranger doive retrouver des conditions de vie qui sont usuelles dans son pays de provenance ne saurait suffire à maintenir son titre de séjour même si ces conditions de vie sont moins avantageuses que celles dont cette personne bénéficie en Suisse (cf. arrêts 2C_1002/2015 du 14 septembre 2016 consid. 3.3; 2C_204/2014 du 5 mai 2014 consid. 7.1). S'agissant enfin des condamnations pénales dont le recourant a fait l'objet, même si aucune d'elles, prises isolément, ne peut être considérée comme une peine privative de liberté de longue durée, elles signifient clairement que le recourant ne parvient pas à se conformer à l'ordre public suisse et que ni la naissance et la présence de ses enfants en Suisse, ni les mises en garde reçues en 2010 par le Service cantonal et en 2012 par le Tribunal administratif fédéral, ni la délivrance d'une autorisation de séjour ne lui ont au final permis de s'amender. Il est vrai que de la date de son mariage à la séparation d'avec son épouse au mois de septembre 2013, les seules infractions commises par le recourant relèvent de la violation de la LEtr. Depuis la séparation, il ne jouit toutefois plus de la stabilité familiale qui semblait l'avoir écarté, provisoirement, de la commission d'autres actes délictueux. Au demeurant, sur les treize condamnations dont le recourant a fait l'objet, cinq d'entre elles ont été prononcées pour des faits commis postérieurement à la séparation d'une part et à la délivrance de son autorisation de séjour d'autre part. Dans ces conditions et quoi qu'en dise le recourant, la commission répétée d'infractions sur toute la durée effective de son séjour en Suisse démontre que celui-ci constitue un danger pour la sécurité et l'ordre publics suisses. C'est partant à bon droit - également sous l'angle des critères d'appréciation de l'art. 31 de l'ordonnance du 24 octobre 2007 relative à l'admission, au séjour et à l'exercice d'une activité lucrative (OASA; RS 142.201) que le recourant invoque et qui se confondent avec ceux qui viennent d'être mentionnés - que le Tribunal cantonal a confirmé le refus d'approuver la prolongation de l'autorisation de séjour du recourant, étant précisé que l'application de l'art. 62 al. 1 let. c LEtr mènerait en l'espèce à la même conclusion.
5.
Les considérants qui précèdent conduisent au rejet du recours. Succombant, le recourant doit supporter les frais judiciaires (art. 66 al. 1 LTF). 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 est rejeté.
2.
Les frais judiciaires, arrêtés à 2'000 fr., sont mis à la charge du recourant.
3.
Le présent arrêt est communiqué au mandataire du recourant, au Service de la population et au Tribunal cantonal du canton de Vaud, Cour de droit administratif et public, ainsi qu'au Secrétariat d'Etat aux migrations.
Lausanne, le 3 août 2017
Au nom de la IIe Cour de droit public
du Tribunal fédéral suisse
Le Président : Seiler
La Greffière : Kleber