{"id":73358,"date":"2024-08-14T02:41:40","date_gmt":"2024-08-13T23:11:40","guid":{"rendered":"https:\/\/nabfollower.com\/blog\/%d8%ad%d8%af%d8%a7%da%a9%d8%ab%d8%b1-%d9%85%d8%b4%da%a9%d9%84-%d8%b2%db%8c%d8%b1%d8%a2%d8%b1%d8%a7%db%8c%d9%87-%d9%88-%d8%a7%d9%84%da%af%d9%88%d8%b1%db%8c%d8%aa%d9%85-%da%a9%d8%a7%d8%af%d8%a7%d9%86\/"},"modified":"2024-08-14T02:41:40","modified_gmt":"2024-08-13T23:11:40","slug":"%d8%ad%d8%af%d8%a7%da%a9%d8%ab%d8%b1-%d9%85%d8%b4%da%a9%d9%84-%d8%b2%db%8c%d8%b1%d8%a2%d8%b1%d8%a7%db%8c%d9%87-%d9%88-%d8%a7%d9%84%da%af%d9%88%d8%b1%db%8c%d8%aa%d9%85-%da%a9%d8%a7%d8%af%d8%a7%d9%86","status":"publish","type":"post","link":"https:\/\/nabfollower.com\/blog\/%d8%ad%d8%af%d8%a7%da%a9%d8%ab%d8%b1-%d9%85%d8%b4%da%a9%d9%84-%d8%b2%db%8c%d8%b1%d8%a2%d8%b1%d8%a7%db%8c%d9%87-%d9%88-%d8%a7%d9%84%da%af%d9%88%d8%b1%db%8c%d8%aa%d9%85-%da%a9%d8%a7%d8%af%d8%a7%d9%86\/","title":{"rendered":"\u062d\u062f\u0627\u06a9\u062b\u0631 \u0645\u0634\u06a9\u0644 \u0632\u06cc\u0631\u0622\u0631\u0627\u06cc\u0647 \u0648 \u0627\u0644\u06af\u0648\u0631\u06cc\u062a\u0645 \u06a9\u0627\u062f\u0627\u0646"},"content":{"rendered":"<p><\/p>\n<div data-article-id=\"1958327\" id=\"article-body\">\n<div id=\"ez-toc-container\" class=\"ez-toc-v2_0_84 counter-hierarchy ez-toc-counter-rtl ez-toc-grey ez-toc-container-direction\">\n<div class=\"ez-toc-title-container\">\n<p class=\"ez-toc-title\" style=\"cursor:inherit\">\u0641\u0647\u0631\u0633\u062a \u0645\u0637\u0627\u0644\u0628<\/p>\n<span class=\"ez-toc-title-toggle\"><a href=\"#\" class=\"ez-toc-pull-right ez-toc-btn ez-toc-btn-xs ez-toc-btn-default ez-toc-toggle\" aria-label=\"Toggle Table of Content\"><span class=\"ez-toc-js-icon-con\"><span class=\"\"><span class=\"eztoc-hide\" style=\"display:none;\">Toggle<\/span><span class=\"ez-toc-icon-toggle-span\"><svg style=\"fill: #999;color:#999\" xmlns=\"http:\/\/www.w3.org\/2000\/svg\" class=\"list-377408\" width=\"20px\" height=\"20px\" viewBox=\"0 0 24 24\" fill=\"none\"><path d=\"M6 6H4v2h2V6zm14 0H8v2h12V6zM4 11h2v2H4v-2zm16 0H8v2h12v-2zM4 16h2v2H4v-2zm16 0H8v2h12v-2z\" fill=\"currentColor\"><\/path><\/svg><svg style=\"fill: #999;color:#999\" class=\"arrow-unsorted-368013\" xmlns=\"http:\/\/www.w3.org\/2000\/svg\" width=\"10px\" height=\"10px\" viewBox=\"0 0 24 24\" version=\"1.2\" baseProfile=\"tiny\"><path d=\"M18.2 9.3l-6.2-6.3-6.2 6.3c-.2.2-.3.4-.3.7s.1.5.3.7c.2.2.4.3.7.3h11c.3 0 .5-.1.7-.3.2-.2.3-.5.3-.7s-.1-.5-.3-.7zM5.8 14.7l6.2 6.3 6.2-6.3c.2-.2.3-.5.3-.7s-.1-.5-.3-.7c-.2-.2-.4-.3-.7-.3h-11c-.3 0-.5.1-.7.3-.2.2-.3.5-.3.7s.1.5.3.7z\"\/><\/svg><\/span><\/span><\/span><\/a><\/span><\/div>\n<nav><ul class='ez-toc-list ez-toc-list-level-1 ' ><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-1\" href=\"https:\/\/nabfollower.com\/blog\/%d8%ad%d8%af%d8%a7%da%a9%d8%ab%d8%b1-%d9%85%d8%b4%da%a9%d9%84-%d8%b2%db%8c%d8%b1%d8%a2%d8%b1%d8%a7%db%8c%d9%87-%d9%88-%d8%a7%d9%84%da%af%d9%88%d8%b1%db%8c%d8%aa%d9%85-%da%a9%d8%a7%d8%af%d8%a7%d9%86\/#%D9%85%D8%B4%DA%A9%D9%84_%D8%AD%D8%AF%D8%A7%DA%A9%D8%AB%D8%B1_%D8%B2%DB%8C%D8%B1%D8%A2%D8%B1%D8%A7%DB%8C%D9%87_%D9%88_%D8%AA%D8%A7%D8%B1%DB%8C%D8%AE%DA%86%D9%87_%D8%A2%D9%86\" >\u0645\u0634\u06a9\u0644 \u062d\u062f\u0627\u06a9\u062b\u0631 \u0632\u06cc\u0631\u0622\u0631\u0627\u06cc\u0647 \u0648 \u062a\u0627\u0631\u06cc\u062e\u0686\u0647 \u0622\u0646<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-2\" href=\"https:\/\/nabfollower.com\/blog\/%d8%ad%d8%af%d8%a7%da%a9%d8%ab%d8%b1-%d9%85%d8%b4%da%a9%d9%84-%d8%b2%db%8c%d8%b1%d8%a2%d8%b1%d8%a7%db%8c%d9%87-%d9%88-%d8%a7%d9%84%da%af%d9%88%d8%b1%db%8c%d8%aa%d9%85-%da%a9%d8%a7%d8%af%d8%a7%d9%86\/#%D9%86%DB%8C%D8%B1%D9%88%DB%8C_%D8%A8%DB%8C_%D8%B1%D8%AD%D9%85_%D8%B1%D9%88%DB%8C%DA%A9%D8%B1%D8%AF_%D8%B3%D8%A7%D8%AF%D9%87_%D9%84%D9%88%D8%AD%D8%A7%D9%86%D9%87_%D8%A8%D8%A7_%D9%BE%DB%8C%DA%86%DB%8C%D8%AF%DA%AF%DB%8C_%D8%B2%D9%85%D8%A7%D9%86%DB%8C_%D9%85%DA%A9%D8%B9%D8%A8%DB%8C\" >\u0646\u06cc\u0631\u0648\u06cc \u0628\u06cc \u0631\u062d\u0645: \u0631\u0648\u06cc\u06a9\u0631\u062f \u0633\u0627\u062f\u0647 \u0644\u0648\u062d\u0627\u0646\u0647 \u0628\u0627 \u067e\u06cc\u0686\u06cc\u062f\u06af\u06cc \u0632\u0645\u0627\u0646\u06cc \u0645\u06a9\u0639\u0628\u06cc<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-3\" href=\"https:\/\/nabfollower.com\/blog\/%d8%ad%d8%af%d8%a7%da%a9%d8%ab%d8%b1-%d9%85%d8%b4%da%a9%d9%84-%d8%b2%db%8c%d8%b1%d8%a2%d8%b1%d8%a7%db%8c%d9%87-%d9%88-%d8%a7%d9%84%da%af%d9%88%d8%b1%db%8c%d8%aa%d9%85-%da%a9%d8%a7%d8%af%d8%a7%d9%86\/#%D8%A8%D9%87%DB%8C%D9%86%D9%87_%D8%B3%D8%A7%D8%B2%DB%8C_On%C2%B2_Grenander_%DB%8C%DA%A9_%DA%AF%D8%A7%D9%85_%D8%A8%D9%87_%D8%AC%D9%84%D9%88\" >\u0628\u0647\u06cc\u0646\u0647 \u0633\u0627\u0632\u06cc O(n\u00b2) Grenander: \u06cc\u06a9 \u06af\u0627\u0645 \u0628\u0647 \u062c\u0644\u0648<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-4\" href=\"https:\/\/nabfollower.com\/blog\/%d8%ad%d8%af%d8%a7%da%a9%d8%ab%d8%b1-%d9%85%d8%b4%da%a9%d9%84-%d8%b2%db%8c%d8%b1%d8%a2%d8%b1%d8%a7%db%8c%d9%87-%d9%88-%d8%a7%d9%84%da%af%d9%88%d8%b1%db%8c%d8%aa%d9%85-%da%a9%d8%a7%d8%af%d8%a7%d9%86\/#Shamoss_Divide_and_Conquer_%D8%AA%D9%82%D8%B3%DB%8C%D9%85_%D9%85%D8%B3%D8%A6%D9%84%D9%87_%D8%A8%D8%B1%D8%A7%DB%8C_On_log_n\" >Shamos&#39;s Divide and Conquer: \u062a\u0642\u0633\u06cc\u0645 \u0645\u0633\u0626\u0644\u0647 \u0628\u0631\u0627\u06cc O(n log n)<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-5\" href=\"https:\/\/nabfollower.com\/blog\/%d8%ad%d8%af%d8%a7%da%a9%d8%ab%d8%b1-%d9%85%d8%b4%da%a9%d9%84-%d8%b2%db%8c%d8%b1%d8%a2%d8%b1%d8%a7%db%8c%d9%87-%d9%88-%d8%a7%d9%84%da%af%d9%88%d8%b1%db%8c%d8%aa%d9%85-%da%a9%d8%a7%d8%af%d8%a7%d9%86\/#%D8%A7%D9%84%DA%AF%D9%88%D8%B1%DB%8C%D8%AA%D9%85_Kadane_The_Elegant_On_Solution\" >\u0627\u0644\u06af\u0648\u0631\u06cc\u062a\u0645 Kadane: The Elegant O(n) Solution<\/a><\/li><\/ul><\/nav><\/div>\n<h2><span class=\"ez-toc-section\" id=\"%D9%85%D8%B4%DA%A9%D9%84_%D8%AD%D8%AF%D8%A7%DA%A9%D8%AB%D8%B1_%D8%B2%DB%8C%D8%B1%D8%A2%D8%B1%D8%A7%DB%8C%D9%87_%D9%88_%D8%AA%D8%A7%D8%B1%DB%8C%D8%AE%DA%86%D9%87_%D8%A2%D9%86\"><\/span>\n<p>  \u0645\u0634\u06a9\u0644 \u062d\u062f\u0627\u06a9\u062b\u0631 \u0632\u06cc\u0631\u0622\u0631\u0627\u06cc\u0647 \u0648 \u062a\u0627\u0631\u06cc\u062e\u0686\u0647 \u0622\u0646<br \/>\n<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<p>\u062f\u0631 \u0627\u0648\u0627\u062e\u0631 \u062f\u0647\u0647 1970\u060c \u0627\u0648\u0644\u0641 \u06af\u0631\u0646\u0627\u0646\u062f\u0631\u060c \u0631\u06cc\u0627\u0636\u06cc\u062f\u0627\u0646 \u0633\u0648\u0626\u062f\u06cc\u060c \u062f\u0631\u0628\u0627\u0631\u0647 \u06cc\u06a9 \u0645\u0633\u0626\u0644\u0647 \u0628\u062d\u062b \u0645\u06cc \u06a9\u0631\u062f: \u0686\u06af\u0648\u0646\u0647 \u0645\u06cc \u062a\u0648\u0627\u0646 \u06cc\u06a9 \u0622\u0631\u0627\u06cc\u0647 2 \u0628\u0639\u062f\u06cc \u0627\u0632 \u062f\u0627\u062f\u0647 \u0647\u0627\u06cc \u062a\u0635\u0648\u06cc\u0631 \u0631\u0627 \u06a9\u0627\u0631\u0622\u0645\u062f\u062a\u0631 \u0627\u0632 \u0646\u06cc\u0631\u0648\u06cc \u0628\u06cc \u0631\u062d\u0645\u0627\u0646\u0647 \u062a\u062c\u0632\u06cc\u0647 \u0648 \u062a\u062d\u0644\u06cc\u0644 \u06a9\u0631\u062f\u061f \u06a9\u0627\u0645\u067e\u06cc\u0648\u062a\u0631\u0647\u0627 \u062f\u0631 \u0622\u0646 \u0632\u0645\u0627\u0646 \u06a9\u0646\u062f \u0628\u0648\u062f\u0646\u062f \u0648 \u062a\u0635\u0627\u0648\u06cc\u0631 \u0646\u0633\u0628\u062a \u0628\u0647 RAM \u0628\u0632\u0631\u06af \u0628\u0648\u062f\u0646\u062f. \u0628\u0631\u0627\u06cc \u062a\u0634\u062f\u06cc\u062f \u0647\u0645\u0647 \u0686\u06cc\u0632\u060c \u062f\u0631 \u0628\u062f\u062a\u0631\u06cc\u0646 \u062d\u0627\u0644\u062a\u060c \u0646\u06cc\u0631\u0648\u06cc \u0628\u06cc \u0631\u062d\u0645\u0627\u0646\u0647 \u0632\u0645\u0627\u0646 O(n^6) \u0631\u0627 \u06af\u0631\u0641\u062a (\u067e\u06cc\u0686\u06cc\u062f\u06af\u06cc \u0632\u0645\u0627\u0646\u06cc \u062c\u0646\u0633\u06cc). <\/p>\n<p>\u0627\u0628\u062a\u062f\u0627\u060c \u06af\u0631\u0646\u0627\u0646\u062f\u06cc\u0631 \u0627\u06cc\u0646 \u0633\u0648\u0627\u0644 \u0631\u0627 \u0633\u0627\u062f\u0647 \u06a9\u0631\u062f: \u0628\u0627 \u062a\u0648\u062c\u0647 \u0628\u0647 \u06cc\u06a9 \u0622\u0631\u0627\u06cc\u0647 \u06cc\u06a9 \u0628\u0639\u062f\u06cc \u0627\u0632 \u0627\u0639\u062f\u0627\u062f\u060c \u0686\u06af\u0648\u0646\u0647 \u0645\u06cc \u062a\u0648\u0627\u0646\u06cc\u062f \u0632\u06cc\u0631\u0622\u0631\u0627\u06cc\u0647 \u0628\u0647 \u0647\u0645 \u067e\u06cc\u0648\u0633\u062a\u0647 \u0631\u0627 \u0628\u0627 \u0628\u06cc\u0634\u062a\u0631\u06cc\u0646 \u0645\u062c\u0645\u0648\u0639 \u0628\u0647 \u0628\u0647\u062a\u0631\u06cc\u0646 \u0646\u062d\u0648 \u067e\u06cc\u062f\u0627 \u06a9\u0646\u06cc\u062f\u061f<\/p>\n<p><img decoding=\"async\" src=\"https:\/\/media.dev.to\/cdn-cgi\/image\/width=800%2Cheight=%2Cfit=scale-down%2Cgravity=auto%2Cformat=auto\/https%3A%2F%2Fdev-to-uploads.s3.amazonaws.com%2Fuploads%2Farticles%2F27zwi4alxlvcdmywc4pb.png\" alt=\"\u0628\u0632\u0631\u06af\u062a\u0631\u06cc\u0646 \u0645\u0634\u06a9\u0644 \u0632\u06cc\u0631\u0622\u0631\u0627\u06cc\u0647\" loading=\"lazy\" width=\"564\" height=\"345\" title=\"\"><\/p>\n<h2><span class=\"ez-toc-section\" id=\"%D9%86%DB%8C%D8%B1%D9%88%DB%8C_%D8%A8%DB%8C_%D8%B1%D8%AD%D9%85_%D8%B1%D9%88%DB%8C%DA%A9%D8%B1%D8%AF_%D8%B3%D8%A7%D8%AF%D9%87_%D9%84%D9%88%D8%AD%D8%A7%D9%86%D9%87_%D8%A8%D8%A7_%D9%BE%DB%8C%DA%86%DB%8C%D8%AF%DA%AF%DB%8C_%D8%B2%D9%85%D8%A7%D9%86%DB%8C_%D9%85%DA%A9%D8%B9%D8%A8%DB%8C\"><\/span>\n<p>  \u0646\u06cc\u0631\u0648\u06cc \u0628\u06cc \u0631\u062d\u0645: \u0631\u0648\u06cc\u06a9\u0631\u062f \u0633\u0627\u062f\u0647 \u0644\u0648\u062d\u0627\u0646\u0647 \u0628\u0627 \u067e\u06cc\u0686\u06cc\u062f\u06af\u06cc \u0632\u0645\u0627\u0646\u06cc \u0645\u06a9\u0639\u0628\u06cc<br \/>\n<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<p>\u0646\u06cc\u0631\u0648\u06cc \u0628\u06cc \u0631\u062d\u0645\u060c \u0646\u06cc\u0645\u06cc \u0627\u0632 \u0632\u0645\u0627\u0646 \u062a\u062c\u0632\u06cc\u0647 \u0648 \u062a\u062d\u0644\u06cc\u0644 \u06cc\u06a9 \u0622\u0631\u0627\u06cc\u0647 \u06cc\u06a9 \u0628\u0639\u062f\u06cc \u0646\u0633\u0628\u062a \u0628\u0647 \u06cc\u06a9 \u0622\u0631\u0627\u06cc\u0647 \u062f\u0648 \u0628\u0639\u062f\u06cc \u062e\u0648\u0627\u0647\u062f \u0628\u0648\u062f\u060c \u0628\u0646\u0627\u0628\u0631\u0627\u06cc\u0646 O(n^3) \u0628\u0631\u0627\u06cc \u0628\u0631\u0631\u0633\u06cc \u0647\u0631 \u062a\u0631\u06a9\u06cc\u0628 \u0645\u0645\u06a9\u0646 (\u067e\u06cc\u0686\u06cc\u062f\u06af\u06cc \u0632\u0645\u0627\u0646\u06cc \u0645\u06a9\u0639\u0628\u06cc).<\/p>\n<div class=\"highlight js-code-highlight\">\n<pre class=\"highlight python\"><code><span class=\"k\">def<\/span> <span class=\"nf\">max_subarray_brute_force<\/span><span class=\"p\">(<\/span><span class=\"n\">arr<\/span><span class=\"p\">):<\/span>\n    <span class=\"n\">max_sum<\/span> <span class=\"o\">=<\/span> <span class=\"n\">arr<\/span><span class=\"p\">[<\/span><span class=\"mi\">0<\/span><span class=\"p\">]<\/span> <span class=\"c1\"># assumes arr has a length\n<\/span>\n    <span class=\"c1\"># iterate over all possible subarrays\n<\/span>    <span class=\"k\">for<\/span> <span class=\"n\">i<\/span> <span class=\"ow\">in<\/span> <span class=\"nf\">range<\/span><span class=\"p\">(<\/span><span class=\"nf\">len<\/span><span class=\"p\">(<\/span><span class=\"n\">arr<\/span><span class=\"p\">)):<\/span>\n        <span class=\"k\">for<\/span> <span class=\"n\">j<\/span> <span class=\"ow\">in<\/span> <span class=\"nf\">range<\/span><span class=\"p\">(<\/span><span class=\"n\">i<\/span><span class=\"p\">,<\/span> <span class=\"nf\">len<\/span><span class=\"p\">(<\/span><span class=\"n\">arr<\/span><span class=\"p\">)):<\/span>\n            <span class=\"n\">current_sum<\/span> <span class=\"o\">=<\/span> <span class=\"mi\">0<\/span>\n            <span class=\"c1\"># sum the elements of the subarray arr[i:j+1]\n<\/span>            <span class=\"k\">for<\/span> <span class=\"n\">k<\/span> <span class=\"ow\">in<\/span> <span class=\"nf\">range<\/span><span class=\"p\">(<\/span><span class=\"n\">i<\/span><span class=\"p\">,<\/span> <span class=\"n\">j<\/span> <span class=\"o\">+<\/span> <span class=\"mi\">1<\/span><span class=\"p\">):<\/span>\n                <span class=\"n\">current_sum<\/span> <span class=\"o\">+=<\/span> <span class=\"n\">arr<\/span><span class=\"p\">[<\/span><span class=\"n\">k<\/span><span class=\"p\">]<\/span>\n            <span class=\"c1\"># update max_sum if the current sum is greater\n<\/span>            <span class=\"n\">max_sum<\/span> <span class=\"o\">=<\/span> <span class=\"nf\">max<\/span><span class=\"p\">(<\/span><span class=\"n\">max_sum<\/span><span class=\"p\">,<\/span> <span class=\"n\">current_sum<\/span><span class=\"p\">)<\/span>\n\n    <span class=\"k\">return<\/span> <span class=\"n\">max_sum<\/span>\n\n<span class=\"nf\">print<\/span><span class=\"p\">(<\/span><span class=\"nf\">max_subarray_brute_force<\/span><span class=\"p\">([<\/span><span class=\"o\">-<\/span><span class=\"mi\">2<\/span><span class=\"p\">,<\/span> <span class=\"o\">-<\/span><span class=\"mi\">3<\/span><span class=\"p\">,<\/span> <span class=\"mi\">4<\/span><span class=\"p\">,<\/span> <span class=\"o\">-<\/span><span class=\"mi\">1<\/span><span class=\"p\">,<\/span> <span class=\"o\">-<\/span><span class=\"mi\">2<\/span><span class=\"p\">,<\/span> <span class=\"mi\">1<\/span><span class=\"p\">,<\/span> <span class=\"mi\">5<\/span><span class=\"p\">,<\/span> <span class=\"o\">-<\/span><span class=\"mi\">3<\/span><span class=\"p\">]),<\/span> <span class=\"sh\">\"<\/span><span class=\"s\">== 7<\/span><span class=\"sh\">\"<\/span><span class=\"p\">)<\/span>\n\n<\/code><\/pre>\n<div class=\"highlight__panel js-actions-panel\">\n<div class=\"highlight__panel-action js-fullscreen-code-action\">\n    <svg xmlns=\"http:\/\/www.w3.org\/2000\/svg\" width=\"20px\" height=\"20px\" viewbox=\"0 0 24 24\" class=\"highlight-action crayons-icon highlight-action--fullscreen-on\"><title>\u0648\u0627\u0631\u062f \u062d\u0627\u0644\u062a \u062a\u0645\u0627\u0645 \u0635\u0641\u062d\u0647 \u0634\u0648\u06cc\u062f<\/title>\n    <path d=\"M16 3h6v6h-2V5h-4V3zM2 3h6v2H4v4H2V3zm18 16v-4h2v6h-6v-2h4zM4 19h4v2H2v-6h2v4z\"\/>\n<\/svg><\/p>\n<p>    <svg xmlns=\"http:\/\/www.w3.org\/2000\/svg\" width=\"20px\" height=\"20px\" viewbox=\"0 0 24 24\" class=\"highlight-action crayons-icon highlight-action--fullscreen-off\"><title>\u0627\u0632 \u062d\u0627\u0644\u062a \u062a\u0645\u0627\u0645 \u0635\u0641\u062d\u0647 \u062e\u0627\u0631\u062c \u0634\u0648\u06cc\u062f<\/title>\n    <path d=\"M18 7h4v2h-6V3h2v4zM8 9H2V7h4V3h2v6zm10 8v4h-2v-6h6v2h-4zM8 15v6H6v-4H2v-2h6z\"\/>\n<\/svg><\/p>\n<\/div>\n<\/div>\n<\/div>\n<h2><span class=\"ez-toc-section\" id=\"%D8%A8%D9%87%DB%8C%D9%86%D9%87_%D8%B3%D8%A7%D8%B2%DB%8C_On%C2%B2_Grenander_%DB%8C%DA%A9_%DA%AF%D8%A7%D9%85_%D8%A8%D9%87_%D8%AC%D9%84%D9%88\"><\/span>\n<p>  \u0628\u0647\u06cc\u0646\u0647 \u0633\u0627\u0632\u06cc O(n\u00b2) Grenander: \u06cc\u06a9 \u06af\u0627\u0645 \u0628\u0647 \u062c\u0644\u0648<br \/>\n<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<p>\u06af\u0631\u0646\u0627\u0646\u062f\u0631 \u0622\u0646 \u0631\u0627 \u0628\u0647 \u0645\u062d\u0644\u0648\u0644 O(n^2) \u0627\u0631\u062a\u0642\u0627 \u062f\u0627\u062f. \u0645\u0646 \u0646\u062a\u0648\u0627\u0646\u0633\u062a\u0645 \u06a9\u062f \u0627\u0648 \u0631\u0627 \u062f\u0631 \u062a\u062d\u0642\u06cc\u0642\u0627\u062a\u0645 \u067e\u06cc\u062f\u0627 \u06a9\u0646\u0645\u060c \u0627\u0645\u0627 \u062d\u062f\u0633 \u0645\u0646 \u0627\u06cc\u0646 \u0627\u0633\u062a \u06a9\u0647 \u0627\u0648 \u0628\u0647 \u0633\u0627\u062f\u06af\u06cc \u0627\u0632 \u062f\u0631\u0648\u0646\u06cc \u062a\u0631\u06cc\u0646 \u062d\u0644\u0642\u0647 \u062e\u0644\u0627\u0635 \u0634\u062f \u06a9\u0647 \u0647\u0645\u0647 \u0627\u0639\u062f\u0627\u062f \u0628\u06cc\u0646 \u062f\u0648 \u0634\u0627\u062e\u0635 \u0631\u0627 \u062c\u0645\u0639 \u0645\u06cc \u06a9\u0646\u062f. \u062f\u0631 \u0639\u0648\u0636\u060c \u0645\u06cc\u200c\u062a\u0648\u0627\u0646\u06cc\u0645 \u062f\u0631 \u062d\u06cc\u0646 \u062a\u06a9\u0631\u0627\u0631 \u0631\u0648\u06cc \u0632\u06cc\u0631\u0622\u0631\u0627\u06cc\u0647\u060c \u06cc\u06a9 \u0645\u062c\u0645\u0648\u0639 \u062f\u0631 \u062d\u0627\u0644 \u0627\u062c\u0631\u0627 \u0646\u06af\u0647 \u062f\u0627\u0631\u06cc\u0645\u060c \u0628\u0646\u0627\u0628\u0631\u0627\u06cc\u0646 \u062a\u0639\u062f\u0627\u062f \u062d\u0644\u0642\u0647\u200c\u0647\u0627 \u0631\u0627 \u0627\u0632 \u0633\u0647 \u0628\u0647 \u062f\u0648 \u06a9\u0627\u0647\u0634 \u0645\u06cc\u200c\u062f\u0647\u06cc\u0645.<\/p>\n<div class=\"highlight js-code-highlight\">\n<pre class=\"highlight python\"><code><span class=\"k\">def<\/span> <span class=\"nf\">max_subarray_optimized<\/span><span class=\"p\">(<\/span><span class=\"n\">arr<\/span><span class=\"p\">):<\/span>\n    <span class=\"n\">max_sum<\/span> <span class=\"o\">=<\/span> <span class=\"n\">arr<\/span><span class=\"p\">[<\/span><span class=\"mi\">0<\/span><span class=\"p\">]<\/span>  <span class=\"c1\"># assumes arr has a length\n<\/span>\n    <span class=\"c1\"># iterate over all possible starting points of the subarray\n<\/span>    <span class=\"k\">for<\/span> <span class=\"n\">i<\/span> <span class=\"ow\">in<\/span> <span class=\"nf\">range<\/span><span class=\"p\">(<\/span><span class=\"nf\">len<\/span><span class=\"p\">(<\/span><span class=\"n\">arr<\/span><span class=\"p\">)):<\/span>\n        <span class=\"n\">current_sum<\/span> <span class=\"o\">=<\/span> <span class=\"mi\">0<\/span>\n        <span class=\"c1\"># sum the elements of the subarray starting from arr[i]\n<\/span>        <span class=\"k\">for<\/span> <span class=\"n\">j<\/span> <span class=\"ow\">in<\/span> <span class=\"nf\">range<\/span><span class=\"p\">(<\/span><span class=\"n\">i<\/span><span class=\"p\">,<\/span> <span class=\"nf\">len<\/span><span class=\"p\">(<\/span><span class=\"n\">arr<\/span><span class=\"p\">)):<\/span>\n            <span class=\"n\">current_sum<\/span> <span class=\"o\">+=<\/span> <span class=\"n\">arr<\/span><span class=\"p\">[<\/span><span class=\"n\">j<\/span><span class=\"p\">]<\/span>\n            <span class=\"c1\"># update max_sum if the current sum is greater\n<\/span>            <span class=\"n\">max_sum<\/span> <span class=\"o\">=<\/span> <span class=\"nf\">max<\/span><span class=\"p\">(<\/span><span class=\"n\">max_sum<\/span><span class=\"p\">,<\/span> <span class=\"n\">current_sum<\/span><span class=\"p\">)<\/span>\n\n    <span class=\"k\">return<\/span> <span class=\"n\">max_sum<\/span>\n<\/code><\/pre>\n<div class=\"highlight__panel js-actions-panel\">\n<div class=\"highlight__panel-action js-fullscreen-code-action\">\n    <svg xmlns=\"http:\/\/www.w3.org\/2000\/svg\" width=\"20px\" height=\"20px\" viewbox=\"0 0 24 24\" class=\"highlight-action crayons-icon highlight-action--fullscreen-on\"><title>\u0648\u0627\u0631\u062f \u062d\u0627\u0644\u062a \u062a\u0645\u0627\u0645 \u0635\u0641\u062d\u0647 \u0634\u0648\u06cc\u062f<\/title>\n    <path d=\"M16 3h6v6h-2V5h-4V3zM2 3h6v2H4v4H2V3zm18 16v-4h2v6h-6v-2h4zM4 19h4v2H2v-6h2v4z\"\/>\n<\/svg><\/p>\n<p>    <svg xmlns=\"http:\/\/www.w3.org\/2000\/svg\" width=\"20px\" height=\"20px\" viewbox=\"0 0 24 24\" class=\"highlight-action crayons-icon highlight-action--fullscreen-off\"><title>\u0627\u0632 \u062d\u0627\u0644\u062a \u062a\u0645\u0627\u0645 \u0635\u0641\u062d\u0647 \u062e\u0627\u0631\u062c \u0634\u0648\u06cc\u062f<\/title>\n    <path d=\"M18 7h4v2h-6V3h2v4zM8 9H2V7h4V3h2v6zm10 8v4h-2v-6h6v2h-4zM8 15v6H6v-4H2v-2h6z\"\/>\n<\/svg><\/p>\n<\/div>\n<\/div>\n<\/div>\n<h2><span class=\"ez-toc-section\" id=\"Shamoss_Divide_and_Conquer_%D8%AA%D9%82%D8%B3%DB%8C%D9%85_%D9%85%D8%B3%D8%A6%D9%84%D9%87_%D8%A8%D8%B1%D8%A7%DB%8C_On_log_n\"><\/span>\n<p>  Shamos&#39;s Divide and Conquer: \u062a\u0642\u0633\u06cc\u0645 \u0645\u0633\u0626\u0644\u0647 \u0628\u0631\u0627\u06cc O(n log n)<br \/>\n<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<p>\u06af\u0631\u0646\u0627\u0646\u062f\u0631 \u0645\u0634\u06a9\u0644 \u0631\u0627 \u0628\u0647 \u062f\u0627\u0646\u0634\u0645\u0646\u062f \u06a9\u0627\u0645\u067e\u06cc\u0648\u062a\u0631 \u0645\u0627\u06cc\u06a9\u0644 \u0634\u0627\u0645\u0648\u0633 \u0646\u0634\u0627\u0646 \u062f\u0627\u062f. \u0634\u0645\u0648\u0633 \u06cc\u06a9 \u0634\u0628 \u0628\u0647 \u0627\u06cc\u0646 \u0645\u0648\u0636\u0648\u0639 \u0641\u06a9\u0631 \u06a9\u0631\u062f \u0648 \u0631\u0648\u0634\u06cc \u0628\u0631\u0627\u06cc \u062a\u0642\u0633\u06cc\u0645 \u0648 \u063a\u0644\u0628\u0647 \u0628\u0647 \u0648\u062c\u0648\u062f \u0622\u0648\u0631\u062f \u06a9\u0647 O(n log n) \u0627\u0633\u062a.<\/p>\n<p>\u0627\u06cc\u0646 \u06a9\u0627\u0645\u0644\u0627 \u0647\u0648\u0634\u0645\u0646\u062f\u0627\u0646\u0647 \u0627\u0633\u062a. \u0627\u06cc\u062f\u0647 \u0627\u06cc\u0646 \u0627\u0633\u062a \u06a9\u0647 \u0622\u0631\u0627\u06cc\u0647 \u0631\u0627 \u0628\u0647 \u062f\u0648 \u0646\u06cc\u0645\u0647 \u062a\u0642\u0633\u06cc\u0645 \u06a9\u0646\u06cc\u0645\u060c \u0633\u067e\u0633 \u0628\u0647 \u0635\u0648\u0631\u062a \u0628\u0627\u0632\u06af\u0634\u062a\u06cc \u062d\u062f\u0627\u06a9\u062b\u0631 \u0645\u062c\u0645\u0648\u0639 \u0632\u06cc\u0631\u0622\u0631\u0627\u06cc\u0647 \u0631\u0627 \u0628\u0631\u0627\u06cc \u0647\u0631 \u0646\u06cc\u0645\u0647 \u0648 \u0647\u0645\u0686\u0646\u06cc\u0646 \u0632\u06cc\u0631\u0622\u0631\u0627\u06cc\u0647 \u0627\u06cc \u06a9\u0647 \u0627\u0632 \u0646\u0642\u0637\u0647 \u0645\u06cc\u0627\u0646\u06cc \u0639\u0628\u0648\u0631 \u0645\u06cc \u06a9\u0646\u062f\u060c \u067e\u06cc\u062f\u0627 \u06a9\u0646\u06cc\u0645.<\/p>\n<div class=\"highlight js-code-highlight\">\n<pre class=\"highlight python\"><code>\n<span class=\"k\">def<\/span> <span class=\"nf\">max_crossing_sum<\/span><span class=\"p\">(<\/span><span class=\"n\">arr<\/span><span class=\"p\">,<\/span> <span class=\"n\">left<\/span><span class=\"p\">,<\/span> <span class=\"n\">mid<\/span><span class=\"p\">,<\/span> <span class=\"n\">right<\/span><span class=\"p\">):<\/span>\n    <span class=\"c1\"># left of mid\n<\/span>    <span class=\"n\">left_sum<\/span> <span class=\"o\">=<\/span> <span class=\"nf\">float<\/span><span class=\"p\">(<\/span><span class=\"sh\">'<\/span><span class=\"s\">-inf<\/span><span class=\"sh\">'<\/span><span class=\"p\">)<\/span>\n    <span class=\"n\">current_sum<\/span> <span class=\"o\">=<\/span> <span class=\"mi\">0<\/span>\n    <span class=\"k\">for<\/span> <span class=\"n\">i<\/span> <span class=\"ow\">in<\/span> <span class=\"nf\">range<\/span><span class=\"p\">(<\/span><span class=\"n\">mid<\/span><span class=\"p\">,<\/span> <span class=\"n\">left<\/span> <span class=\"o\">-<\/span> <span class=\"mi\">1<\/span><span class=\"p\">,<\/span> <span class=\"o\">-<\/span><span class=\"mi\">1<\/span><span class=\"p\">):<\/span>\n        <span class=\"n\">current_sum<\/span> <span class=\"o\">+=<\/span> <span class=\"n\">arr<\/span><span class=\"p\">[<\/span><span class=\"n\">i<\/span><span class=\"p\">]<\/span>\n        <span class=\"n\">left_sum<\/span> <span class=\"o\">=<\/span> <span class=\"nf\">max<\/span><span class=\"p\">(<\/span><span class=\"n\">left_sum<\/span><span class=\"p\">,<\/span> <span class=\"n\">current_sum<\/span><span class=\"p\">)<\/span>\n\n    <span class=\"c1\"># right of mid\n<\/span>    <span class=\"n\">right_sum<\/span> <span class=\"o\">=<\/span> <span class=\"nf\">float<\/span><span class=\"p\">(<\/span><span class=\"sh\">'<\/span><span class=\"s\">inf<\/span><span class=\"sh\">'<\/span><span class=\"p\">)<\/span>\n    <span class=\"n\">current_sum<\/span> <span class=\"o\">=<\/span> <span class=\"mi\">0<\/span>\n    <span class=\"k\">for<\/span> <span class=\"n\">i<\/span> <span class=\"ow\">in<\/span> <span class=\"nf\">range<\/span><span class=\"p\">(<\/span><span class=\"n\">mid<\/span> <span class=\"o\">+<\/span> <span class=\"mi\">1<\/span><span class=\"p\">,<\/span> <span class=\"n\">right<\/span> <span class=\"o\">+<\/span> <span class=\"mi\">1<\/span><span class=\"p\">):<\/span>\n        <span class=\"n\">current_sum<\/span> <span class=\"o\">+=<\/span> <span class=\"n\">arr<\/span><span class=\"p\">[<\/span><span class=\"n\">i<\/span><span class=\"p\">]<\/span>\n        <span class=\"n\">right_sum<\/span> <span class=\"o\">=<\/span> <span class=\"nf\">max<\/span><span class=\"p\">(<\/span><span class=\"n\">right_sum<\/span><span class=\"p\">,<\/span> <span class=\"n\">current_sum<\/span><span class=\"p\">)<\/span>\n\n    <span class=\"c1\"># sum of elements on the left and right of mid, which is the maximum sum that crosses the midpoint\n<\/span>    <span class=\"k\">return<\/span> <span class=\"n\">left_sum<\/span> <span class=\"o\">+<\/span> <span class=\"n\">right_sum<\/span>\n\n<span class=\"k\">def<\/span> <span class=\"nf\">max_subarray_divide_and_conquer<\/span><span class=\"p\">(<\/span><span class=\"n\">arr<\/span><span class=\"p\">,<\/span> <span class=\"n\">left<\/span><span class=\"p\">,<\/span> <span class=\"n\">right<\/span><span class=\"p\">):<\/span>\n    <span class=\"c1\"># base case: only one element\n<\/span>    <span class=\"k\">if<\/span> <span class=\"n\">left<\/span> <span class=\"o\">==<\/span> <span class=\"n\">right<\/span><span class=\"p\">:<\/span>\n        <span class=\"k\">return<\/span> <span class=\"n\">arr<\/span><span class=\"p\">[<\/span><span class=\"n\">left<\/span><span class=\"p\">]<\/span>\n\n    <span class=\"c1\"># find the midpoint\n<\/span>    <span class=\"n\">mid<\/span> <span class=\"o\">=<\/span> <span class=\"p\">(<\/span><span class=\"n\">left<\/span> <span class=\"o\">+<\/span> <span class=\"n\">right<\/span><span class=\"p\">)<\/span> <span class=\"o\">\/\/<\/span> <span class=\"mi\">2<\/span>\n\n    <span class=\"c1\"># recursively find the maximum subarray sum for the left and right halves\n<\/span>    <span class=\"n\">left_sum<\/span> <span class=\"o\">=<\/span> <span class=\"nf\">max_subarray_divide_and_conquer<\/span><span class=\"p\">(<\/span><span class=\"n\">arr<\/span><span class=\"p\">,<\/span> <span class=\"n\">left<\/span><span class=\"p\">,<\/span> <span class=\"n\">mid<\/span><span class=\"p\">)<\/span>\n    <span class=\"n\">right_sum<\/span> <span class=\"o\">=<\/span> <span class=\"nf\">max_subarray_divide_and_conquer<\/span><span class=\"p\">(<\/span><span class=\"n\">arr<\/span><span class=\"p\">,<\/span> <span class=\"n\">mid<\/span> <span class=\"o\">+<\/span> <span class=\"mi\">1<\/span><span class=\"p\">,<\/span> <span class=\"n\">right<\/span><span class=\"p\">)<\/span>\n    <span class=\"n\">cross_sum<\/span> <span class=\"o\">=<\/span> <span class=\"nf\">max_crossing_sum<\/span><span class=\"p\">(<\/span><span class=\"n\">arr<\/span><span class=\"p\">,<\/span> <span class=\"n\">left<\/span><span class=\"p\">,<\/span> <span class=\"n\">mid<\/span><span class=\"p\">,<\/span> <span class=\"n\">right<\/span><span class=\"p\">)<\/span>\n\n    <span class=\"c1\"># return the maximum of the three possible cases\n<\/span>    <span class=\"k\">return<\/span> <span class=\"nf\">max<\/span><span class=\"p\">(<\/span><span class=\"n\">left_sum<\/span><span class=\"p\">,<\/span> <span class=\"n\">right_sum<\/span><span class=\"p\">,<\/span> <span class=\"n\">cross_sum<\/span><span class=\"p\">)<\/span>\n\n<span class=\"k\">def<\/span> <span class=\"nf\">max_subarray<\/span><span class=\"p\">(<\/span><span class=\"n\">arr<\/span><span class=\"p\">):<\/span>\n    <span class=\"k\">return<\/span> <span class=\"nf\">max_subarray_divide_and_conquer<\/span><span class=\"p\">(<\/span><span class=\"n\">arr<\/span><span class=\"p\">,<\/span> <span class=\"mi\">0<\/span><span class=\"p\">,<\/span> <span class=\"nf\">len<\/span><span class=\"p\">(<\/span><span class=\"n\">arr<\/span><span class=\"p\">)<\/span> <span class=\"o\">-<\/span> <span class=\"mi\">1<\/span><span class=\"p\">)<\/span>\n\n\n<span class=\"nf\">print<\/span><span class=\"p\">(<\/span><span class=\"nf\">max_subarray<\/span><span class=\"p\">([<\/span><span class=\"o\">-<\/span><span class=\"mi\">2<\/span><span class=\"p\">,<\/span> <span class=\"o\">-<\/span><span class=\"mi\">3<\/span><span class=\"p\">,<\/span> <span class=\"mi\">4<\/span><span class=\"p\">,<\/span> <span class=\"o\">-<\/span><span class=\"mi\">1<\/span><span class=\"p\">,<\/span> <span class=\"o\">-<\/span><span class=\"mi\">2<\/span><span class=\"p\">,<\/span> <span class=\"mi\">1<\/span><span class=\"p\">,<\/span> <span class=\"mi\">5<\/span><span class=\"p\">,<\/span> <span class=\"o\">-<\/span><span class=\"mi\">3<\/span><span class=\"p\">]),<\/span> <span class=\"sh\">\"<\/span><span class=\"s\">== 7<\/span><span class=\"sh\">\"<\/span><span class=\"p\">)<\/span>\n\n\n<\/code><\/pre>\n<div class=\"highlight__panel js-actions-panel\">\n<div class=\"highlight__panel-action js-fullscreen-code-action\">\n    <svg xmlns=\"http:\/\/www.w3.org\/2000\/svg\" width=\"20px\" height=\"20px\" viewbox=\"0 0 24 24\" class=\"highlight-action crayons-icon highlight-action--fullscreen-on\"><title>\u0648\u0627\u0631\u062f \u062d\u0627\u0644\u062a \u062a\u0645\u0627\u0645 \u0635\u0641\u062d\u0647 \u0634\u0648\u06cc\u062f<\/title>\n    <path d=\"M16 3h6v6h-2V5h-4V3zM2 3h6v2H4v4H2V3zm18 16v-4h2v6h-6v-2h4zM4 19h4v2H2v-6h2v4z\"\/>\n<\/svg><\/p>\n<p>    <svg xmlns=\"http:\/\/www.w3.org\/2000\/svg\" width=\"20px\" height=\"20px\" viewbox=\"0 0 24 24\" class=\"highlight-action crayons-icon highlight-action--fullscreen-off\"><title>\u0627\u0632 \u062d\u0627\u0644\u062a \u062a\u0645\u0627\u0645 \u0635\u0641\u062d\u0647 \u062e\u0627\u0631\u062c \u0634\u0648\u06cc\u062f<\/title>\n    <path d=\"M18 7h4v2h-6V3h2v4zM8 9H2V7h4V3h2v6zm10 8v4h-2v-6h6v2h-4zM8 15v6H6v-4H2v-2h6z\"\/>\n<\/svg><\/p>\n<\/div>\n<\/div>\n<\/div>\n<p>\u0627\u06cc\u0646 \u067e\u06cc\u0686\u06cc\u062f\u06af\u06cc \u0632\u0645\u0627\u0646\u06cc \u0631\u0627 \u0628\u0647 \u0632\u0645\u0627\u0646 O(nlogn) \u06a9\u0627\u0647\u0634 \u0645\u06cc \u062f\u0647\u062f \u0632\u06cc\u0631\u0627 \u0627\u0628\u062a\u062f\u0627 \u0622\u0631\u0627\u06cc\u0647 \u0628\u0647 \u062f\u0648 \u0646\u06cc\u0645\u0647 (O(logn)) \u062a\u0642\u0633\u06cc\u0645 \u0645\u06cc \u0634\u0648\u062f \u0648 \u0633\u067e\u0633 \u06cc\u0627\u0641\u062a\u0646 \u062d\u062f\u0627\u06a9\u062b\u0631 \u0632\u06cc\u0631\u0622\u0631\u0627\u06cc\u0647 \u0645\u062a\u0642\u0627\u0637\u0639 \u0628\u0647 O(n) \u0646\u06cc\u0627\u0632 \u062f\u0627\u0631\u062f.<\/p>\n<h2><span class=\"ez-toc-section\" id=\"%D8%A7%D9%84%DA%AF%D9%88%D8%B1%DB%8C%D8%AA%D9%85_Kadane_The_Elegant_On_Solution\"><\/span>\n<p>  \u0627\u0644\u06af\u0648\u0631\u06cc\u062a\u0645 Kadane: The Elegant O(n) Solution<br \/>\n<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<p>Stastician Jay Kadane \u0628\u0647 \u06a9\u062f \u0646\u06af\u0627\u0647 \u06a9\u0631\u062f \u0648 \u0628\u0644\u0627\u0641\u0627\u0635\u0644\u0647 \u0645\u062a\u0648\u062c\u0647 \u0634\u062f \u06a9\u0647 \u0631\u0627\u0647 \u062d\u0644 Shamos \u062f\u0631 \u0627\u0633\u062a\u0641\u0627\u062f\u0647 \u0627\u0632 \u0645\u0647\u0627\u0631 \u0645\u062c\u0627\u0648\u0631\u062a \u0628\u0647 \u0639\u0646\u0648\u0627\u0646 \u0628\u062e\u0634\u06cc \u0627\u0632 \u0631\u0627\u0647 \u062d\u0644 \u0634\u06a9\u0633\u062a \u062e\u0648\u0631\u062f\u0647 \u0627\u0633\u062a.<\/p>\n<p>\u0627\u06cc\u0646 \u0686\u06cc\u0632\u06cc \u0627\u0633\u062a \u06a9\u0647 \u0627\u0648 \u0645\u062a\u0648\u062c\u0647 \u0634\u062f<\/p>\n<p>-\u0627\u06af\u0631 \u06cc\u06a9 \u0622\u0631\u0627\u06cc\u0647 \u0641\u0642\u0637 \u0627\u0639\u062f\u0627\u062f \u0645\u0646\u0641\u06cc \u062f\u0627\u0634\u062a\u0647 \u0628\u0627\u0634\u062f\u060c \u0628\u0627 \u0641\u0631\u0636 \u0627\u06cc\u0646\u06a9\u0647 \u0627\u062c\u0627\u0632\u0647 \u0646\u062f\u0627\u0631\u06cc\u0645 \u0632\u06cc\u0631\u0622\u0631\u0627\u06cc\u0647 \u0647\u0627\u06cc \u062e\u0627\u0644\u06cc \u0631\u0627 \u0645\u062c\u0627\u0632 \u0646\u06a9\u0646\u06cc\u0645\u060c \u067e\u0627\u0633\u062e \u0647\u0645\u06cc\u0634\u0647 \u0628\u0632\u0631\u06af\u062a\u0631\u06cc\u0646 \u0639\u062f\u062f \u062f\u0631 \u0622\u0631\u0627\u06cc\u0647 \u062e\u0648\u0627\u0647\u062f \u0628\u0648\u062f.<\/p>\n<p>-\u0627\u06af\u0631 \u06cc\u06a9 \u0622\u0631\u0627\u06cc\u0647 \u0641\u0642\u0637 \u062f\u0627\u0631\u0627\u06cc \u0627\u0639\u062f\u0627\u062f \u0645\u062b\u0628\u062a \u0628\u0627\u0634\u062f\u060c \u067e\u0627\u0633\u062e \u0647\u0645\u06cc\u0634\u0647 \u062c\u0645\u0639 \u06a9\u0631\u062f\u0646 \u06a9\u0644 \u0622\u0631\u0627\u06cc\u0647 \u062e\u0648\u0627\u0647\u062f \u0628\u0648\u062f.<\/p>\n<p>-\u0627\u06af\u0631 \u0622\u0631\u0627\u06cc\u0647 \u0627\u06cc \u0627\u0632 \u0627\u0639\u062f\u0627\u062f \u0645\u062b\u0628\u062a \u0648 \u0645\u0646\u0641\u06cc \u062f\u0627\u0631\u06cc\u062f\u060c \u0645\u06cc \u062a\u0648\u0627\u0646\u06cc\u062f \u06af\u0627\u0645 \u0628\u0647 \u06af\u0627\u0645 \u0622\u0631\u0627\u06cc\u0647 \u0631\u0627 \u0637\u06cc \u06a9\u0646\u06cc\u062f. \u0627\u06af\u0631 \u062f\u0631 \u0647\u0631 \u0646\u0642\u0637\u0647 \u0627\u06cc \u0639\u062f\u062f\u06cc \u06a9\u0647 \u0628\u0647 \u0622\u0646 \u0646\u06af\u0627\u0647 \u0645\u06cc \u06a9\u0646\u06cc\u062f \u0628\u0632\u0631\u06af\u062a\u0631 \u0627\u0632 \u0645\u062c\u0645\u0648\u0639 \u062a\u0645\u0627\u0645 \u0627\u0639\u062f\u0627\u062f \u0642\u0628\u0644 \u0627\u0632 \u0622\u0646 \u0628\u0627\u0634\u062f\u060c \u0631\u0627\u0647 \u062d\u0644 \u0646\u0645\u06cc \u062a\u0648\u0627\u0646\u062f \u0634\u0627\u0645\u0644 \u0647\u06cc\u0686 \u06cc\u06a9 \u0627\u0632 \u0627\u0639\u062f\u0627\u062f \u0642\u0628\u0644\u06cc \u0628\u0627\u0634\u062f. \u0628\u0646\u0627\u0628\u0631\u0627\u06cc\u0646\u060c \u0634\u0645\u0627 \u06cc\u06a9 \u0645\u062c\u0645\u0648\u0639 \u062c\u062f\u06cc\u062f \u0631\u0627 \u0627\u0632 \u0639\u062f\u062f \u0641\u0639\u0644\u06cc \u0634\u0631\u0648\u0639 \u0645\u06cc\u200c\u06a9\u0646\u06cc\u062f\u060c \u062f\u0631 \u062d\u0627\u0644\u06cc \u06a9\u0647 \u062d\u062f\u0627\u06a9\u062b\u0631 \u0645\u0628\u0644\u063a\u06cc \u0631\u0627 \u06a9\u0647 \u062a\u0627\u06a9\u0646\u0648\u0646 \u0628\u0627 \u0622\u0646 \u0645\u0648\u0627\u062c\u0647 \u0634\u062f\u0647\u200c\u0627\u06cc\u062f \u0631\u0627 \u067e\u06cc\u06af\u06cc\u0631\u06cc \u0645\u06cc\u200c\u06a9\u0646\u06cc\u062f.<\/p>\n<div class=\"highlight js-code-highlight\">\n<pre class=\"highlight python\"><code>\n\n<span class=\"nf\">maxSubArray<\/span><span class=\"p\">(<\/span><span class=\"n\">nums<\/span><span class=\"p\">):<\/span>\n    <span class=\"c1\"># avoiding type errors or index out of bounds errors\n<\/span>    <span class=\"k\">if<\/span> <span class=\"n\">nums<\/span> <span class=\"ow\">is<\/span> <span class=\"bp\">None<\/span> <span class=\"ow\">or<\/span> <span class=\"nf\">len<\/span><span class=\"p\">(<\/span><span class=\"n\">nums<\/span><span class=\"p\">)<\/span> <span class=\"o\">==<\/span> <span class=\"mi\">0<\/span><span class=\"p\">:<\/span>\n        <span class=\"k\">return<\/span> <span class=\"mi\">0<\/span>\n\n\n    <span class=\"n\">max_sum<\/span> <span class=\"o\">=<\/span> <span class=\"n\">nums<\/span><span class=\"p\">[<\/span><span class=\"mi\">0<\/span><span class=\"p\">]<\/span>  <span class=\"c1\"># max sum can't be smaller than any given element\n<\/span>    <span class=\"n\">curr_sum<\/span> <span class=\"o\">=<\/span> <span class=\"mi\">0<\/span>\n\n    <span class=\"c1\"># Kadane's algorithm\n<\/span>    <span class=\"k\">for<\/span> <span class=\"n\">num<\/span> <span class=\"ow\">in<\/span> <span class=\"n\">nums<\/span><span class=\"p\">:<\/span>\n        <span class=\"n\">curr_sum<\/span> <span class=\"o\">=<\/span> <span class=\"nf\">max<\/span><span class=\"p\">(<\/span><span class=\"n\">num<\/span><span class=\"p\">,<\/span> <span class=\"n\">curr_sum<\/span> <span class=\"o\">+<\/span> <span class=\"n\">num<\/span><span class=\"p\">)<\/span>\n        <span class=\"n\">max_sum<\/span> <span class=\"o\">=<\/span> <span class=\"nf\">max<\/span><span class=\"p\">(<\/span><span class=\"n\">curr_sum<\/span><span class=\"p\">,<\/span> <span class=\"n\">max_sum<\/span><span class=\"p\">)<\/span>\n    <span class=\"k\">return<\/span> <span class=\"n\">max_sum<\/span>\n\n\n<\/code><\/pre>\n<div class=\"highlight__panel js-actions-panel\">\n<div class=\"highlight__panel-action js-fullscreen-code-action\">\n    <svg xmlns=\"http:\/\/www.w3.org\/2000\/svg\" width=\"20px\" height=\"20px\" viewbox=\"0 0 24 24\" class=\"highlight-action crayons-icon highlight-action--fullscreen-on\"><title>\u0648\u0627\u0631\u062f \u062d\u0627\u0644\u062a \u062a\u0645\u0627\u0645 \u0635\u0641\u062d\u0647 \u0634\u0648\u06cc\u062f<\/title>\n    <path d=\"M16 3h6v6h-2V5h-4V3zM2 3h6v2H4v4H2V3zm18 16v-4h2v6h-6v-2h4zM4 19h4v2H2v-6h2v4z\"\/>\n<\/svg><\/p>\n<p>    <svg xmlns=\"http:\/\/www.w3.org\/2000\/svg\" width=\"20px\" height=\"20px\" viewbox=\"0 0 24 24\" class=\"highlight-action crayons-icon highlight-action--fullscreen-off\"><title>\u0627\u0632 \u062d\u0627\u0644\u062a \u062a\u0645\u0627\u0645 \u0635\u0641\u062d\u0647 \u062e\u0627\u0631\u062c \u0634\u0648\u06cc\u062f<\/title>\n    <path d=\"M18 7h4v2h-6V3h2v4zM8 9H2V7h4V3h2v6zm10 8v4h-2v-6h6v2h-4zM8 15v6H6v-4H2v-2h6z\"\/>\n<\/svg><\/p>\n<\/div>\n<\/div>\n<\/div>\n<p>\u0686\u06cc\u0632\u06cc \u06a9\u0647 \u0645\u0646 \u062f\u0631 \u0645\u0648\u0631\u062f \u0627\u06cc\u0646 \u0627\u0644\u06af\u0648\u0631\u06cc\u062a\u0645 \u062f\u0648\u0633\u062a \u062f\u0627\u0631\u0645 \u0627\u06cc\u0646 \u0627\u0633\u062a \u06a9\u0647 \u0645\u06cc \u062a\u0648\u0627\u0646 \u0622\u0646 \u0631\u0627 \u0628\u0631\u0627\u06cc \u0628\u0633\u06cc\u0627\u0631\u06cc \u0627\u0632 \u0645\u0634\u06a9\u0644\u0627\u062a \u062f\u06cc\u06af\u0631 \u0627\u0639\u0645\u0627\u0644 \u06a9\u0631\u062f. \u0633\u0639\u06cc \u06a9\u0646\u06cc\u062f \u0622\u0646 \u0631\u0627 \u0628\u0631\u0627\u06cc \u062d\u0644 \u0627\u06cc\u0646 \u0645\u0634\u06a9\u0644\u0627\u062a LeetCode \u062a\u0637\u0628\u06cc\u0642 \u062f\u0647\u06cc\u062f:<\/p>\n<p>\u06cc\u06a9 \u0647\u0627 \u0648 \u0635\u0641\u0631\u0647\u0627<br \/>\u0645\u0627\u06a9\u0632\u06cc\u0645\u0645 \u062c\u0645\u0639 \u062f\u0627\u06cc\u0631\u0647 \u0627\u06cc \u0641\u0631\u0639\u06cc<br \/>\u062d\u062f\u0627\u0642\u0644 \u0627\u0646\u062f\u0627\u0632\u0647 \u0633\u0627\u0628\u0631\u0627\u06cc \u062c\u0645\u0639<br \/>\u062d\u062f\u0627\u06a9\u062b\u0631 \u0645\u062c\u0645\u0648\u0639 \u0632\u06cc\u0631\u0622\u0631\u0627\u06cc\u0647 \u0635\u0639\u0648\u062f\u06cc<br \/>\u062d\u062f\u0627\u06a9\u062b\u0631 \u0645\u062d\u0635\u0648\u0644 \u0641\u0631\u0639\u06cc<br \/>\u0645\u062c\u0645\u0648\u0639 \u0632\u06cc\u0631\u0622\u0628\u06cc \u067e\u06cc\u0648\u0633\u062a\u0647<br \/>\u062d\u062f\u0627\u06a9\u062b\u0631 \u0645\u062c\u0645\u0648\u0639 \u0645\u062a\u0646\u0627\u0648\u0628 \u0641\u0631\u0639\u06cc (\u062d\u0642 \u0628\u06cc\u0645\u0647)<br \/>\u062d\u062f\u0627\u06a9\u062b\u0631 \u0645\u062c\u0645\u0648\u0639 \u0645\u0633\u062a\u0637\u06cc\u0644 \u0628\u062f\u0648\u0646 \u0628\u0632\u0631\u06af\u062a\u0631 \u0627\u0632 K<\/p>\n<\/p><\/div>\n","protected":false},"excerpt":{"rendered":"<p>\u0645\u0634\u06a9\u0644 \u062d\u062f\u0627\u06a9\u062b\u0631 \u0632\u06cc\u0631\u0622\u0631\u0627\u06cc\u0647 \u0648 \u062a\u0627\u0631\u06cc\u062e\u0686\u0647 \u0622\u0646 \u062f\u0631 \u0627\u0648\u0627\u062e\u0631 \u062f\u0647\u0647 1970\u060c \u0627\u0648\u0644\u0641 \u06af\u0631\u0646\u0627\u0646\u062f\u0631\u060c \u0631\u06cc\u0627\u0636\u06cc\u062f\u0627\u0646 \u0633\u0648\u0626\u062f\u06cc\u060c \u062f\u0631\u0628\u0627\u0631\u0647 \u06cc\u06a9 \u0645\u0633\u0626\u0644\u0647 \u0628\u062d\u062b \u0645\u06cc \u06a9\u0631\u062f: \u0686\u06af\u0648\u0646\u0647 \u0645\u06cc \u062a\u0648\u0627\u0646 \u06cc\u06a9 \u0622\u0631\u0627\u06cc\u0647 2 \u0628\u0639\u062f\u06cc \u0627\u0632 \u062f\u0627\u062f\u0647 \u0647\u0627\u06cc \u062a\u0635\u0648\u06cc\u0631 \u0631\u0627 \u06a9\u0627\u0631\u0622\u0645\u062f\u062a\u0631 \u0627\u0632 \u0646\u06cc\u0631\u0648\u06cc \u0628\u06cc \u0631\u062d\u0645\u0627\u0646\u0647 \u062a\u062c\u0632\u06cc\u0647 \u0648 \u062a\u062d\u0644\u06cc\u0644 \u06a9\u0631\u062f\u061f \u06a9\u0627\u0645\u067e\u06cc\u0648\u062a\u0631\u0647\u0627 \u062f\u0631 \u0622\u0646 \u0632\u0645\u0627\u0646 \u06a9\u0646\u062f \u0628\u0648\u062f\u0646\u062f \u0648 \u062a\u0635\u0627\u0648\u06cc\u0631 \u0646\u0633\u0628\u062a \u0628\u0647 RAM \u0628\u0632\u0631\u06af \u0628\u0648\u062f\u0646\u062f. \u0628\u0631\u0627\u06cc &hellip;<\/p>\n","protected":false},"author":2,"featured_media":73359,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"fifu_image_url":"https:\/\/media.dev.to\/cdn-cgi\/image\/width=1000,height=500,fit=cover,gravity=auto,format=auto\/https%3A%2F%2Fdev-to-uploads.s3.amazonaws.com%2Fuploads%2Farticles%2Fndm5w8q6sifr1y4i9h58.png","fifu_image_alt":"","footnotes":""},"categories":[339],"tags":[],"class_list":["post-73358","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-dev"],"_links":{"self":[{"href":"https:\/\/nabfollower.com\/blog\/wp-json\/wp\/v2\/posts\/73358","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/nabfollower.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/nabfollower.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/nabfollower.com\/blog\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/nabfollower.com\/blog\/wp-json\/wp\/v2\/comments?post=73358"}],"version-history":[{"count":0,"href":"https:\/\/nabfollower.com\/blog\/wp-json\/wp\/v2\/posts\/73358\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/nabfollower.com\/blog\/wp-json\/wp\/v2\/media\/73359"}],"wp:attachment":[{"href":"https:\/\/nabfollower.com\/blog\/wp-json\/wp\/v2\/media?parent=73358"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/nabfollower.com\/blog\/wp-json\/wp\/v2\/categories?post=73358"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/nabfollower.com\/blog\/wp-json\/wp\/v2\/tags?post=73358"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}