{"id":420,"date":"2020-03-30T05:05:00","date_gmt":"2020-03-30T05:05:00","guid":{"rendered":"https:\/\/danwritescode.com\/?p=420"},"modified":"2020-06-26T05:29:20","modified_gmt":"2020-06-26T05:29:20","slug":"max-profit-codility-100-correct-solution","status":"publish","type":"post","link":"https:\/\/danwritescode.com\/max-profit-codility-100-correct-solution\/","title":{"rendered":"Max Profit Codility &#8211; 100% Correct Solution"},"content":{"rendered":"\n<p>The Max Profit Codility challenge put me to a solid test in order to find a O(N) solution.<\/p>\n\n\n\n<p>In the end I found the following algorithm:<\/p>\n\n\n\n<p>I iterated the array of stock prices. At each point I calculated the maximum profit that could be obtained in  point and the minimum price met until that point. Then I compared the maximum so far with the current maximum possible profit and kept the biggest one in the maxSoFar value.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\">Solution in Javascript with O(N) complexity<\/h2>\n\n\n\n<pre class=\"wp-block-code\"><code lang=\"javascript\" class=\"language-javascript\">function solution(A) {\n    let maxSoFar = maxEndingHere = 0;\n    let minPrice = A[0]\n    for (let i = 0; i &lt; A.length; i++){\n        maxEndingHere = Math.max(0, A[i]-minPrice)\n        minPrice = Math.min(minPrice, A[i])\n        maxSoFar = Math.max(maxEndingHere, maxSoFar)\n    } \n    return(maxSoFar)\n}<\/code><\/pre>\n\n\n\n<p>Here is a <a href=\"https:\/\/app.codility.com\/demo\/results\/training5P9WM4-SEV\/\" target=\"_blank\" aria-label=\" (opens in a new tab)\" rel=\"noreferrer noopener\" class=\"rank-math-link\">link to the report and the description<\/a> of the problem.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>The Max Profit Codility challenge put me to a solid test in order to find a O(N) solution. In the end I found the following algorithm: I iterated the array of stock prices. At each point I calculated the maximum profit that could be obtained in point and the minimum price met until that point. Then I compared the maximum so far with the current maximum possible profit and kept the biggest one in the maxSoFar value. Solution in Javascript with O(N) complexity Here is a link to the report and the description of the problem.<\/p>\n","protected":false},"author":1,"featured_media":423,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[12,5,6],"tags":[],"_links":{"self":[{"href":"https:\/\/danwritescode.com\/wp-json\/wp\/v2\/posts\/420"}],"collection":[{"href":"https:\/\/danwritescode.com\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/danwritescode.com\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/danwritescode.com\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/danwritescode.com\/wp-json\/wp\/v2\/comments?post=420"}],"version-history":[{"count":0,"href":"https:\/\/danwritescode.com\/wp-json\/wp\/v2\/posts\/420\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/danwritescode.com\/wp-json\/wp\/v2\/media\/423"}],"wp:attachment":[{"href":"https:\/\/danwritescode.com\/wp-json\/wp\/v2\/media?parent=420"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/danwritescode.com\/wp-json\/wp\/v2\/categories?post=420"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/danwritescode.com\/wp-json\/wp\/v2\/tags?post=420"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}