{"id":3596,"date":"2021-11-12T11:54:47","date_gmt":"2021-11-12T06:24:47","guid":{"rendered":"https:\/\/www.interviewbit.com\/blog\/?p=3596"},"modified":"2021-11-12T18:08:20","modified_gmt":"2021-11-12T12:38:20","slug":"maximum-product-subarray-problem","status":"publish","type":"post","link":"https:\/\/www.interviewbit.com\/blog\/maximum-product-subarray-problem\/","title":{"rendered":"Maximum Product Subarray Problem"},"content":{"rendered":"\n<div class=\"gutentoc tocactive ullist\"><div class=\"gutentoc-toc-wrap\"><div class=\"gutentoc-toc-title-wrap\"><div class=\"gutentoc-toc-title\">Table Of Contents<\/div><div id=\"open\" class=\"text_open\">show<\/div><\/div><div id=\"toclist\"><div class=\"gutentoc-toc__list-wrap\"><ul class=\"gutentoc-toc__list\"><li><a href=\"#approach-1-brute-force\">Approach 1: Brute Force<\/a><\/li><ul class=\"gutentoc-toc__list\"><li><a href=\"#c-code\">C++ Code<\/a><\/li><li><a href=\"#java-code\">Java Code<\/a><\/li><li><a href=\"#python-code\">Python Code<\/a><\/li><\/ul><li><a href=\"#approach-2-dynamic-programming\">Approach 2: Dynamic Programming<\/a><\/li><ul class=\"gutentoc-toc__list\"><li><a href=\"#c-code\">C++ Code<\/a><\/li><li><a href=\"#java-code\">Java Code<\/a><\/li><li><a href=\"#python-code\">Python Code<\/a><\/li><\/ul><li><a href=\"#faq\">FAQ<\/a><\/li><\/ul><\/div><\/div><\/div><\/div>\n\n\n\n<p>Given an array <strong>A[]<\/strong> of <strong>N<\/strong> positive integers. The task is to find a non empty subarray having the largest product and return the <strong>product<\/strong>.<\/p>\n\n\n\n<p><strong>Examples:<\/strong><\/p>\n\n\n\n<p><strong>Input: A[] <\/strong>= [2, 3, -2, 4]<br><strong>Output:<\/strong> 6<br><strong>Explanation: <\/strong>The maximum product subarray is [2, 3] = 6<\/p>\n\n\n\n<p><strong>Input: <\/strong>&nbsp;A[] = [-2, 0, -1]\n\n\n\n<p><strong>Output:<\/strong> 0<\/p>\n\n\n\n<h2 id=\"approach-1-brute-force\">Approach 1: Brute Force<\/h2>\n\n\n\n<p>A simple approach to solve this problem is to find all possible subarrays of the given input array and maximize the product of all subarrays found so far.<br><br><strong>Algorithm :<\/strong><\/p>\n\n\n\n<ul><li>Initialise a variable <strong>result = A[0] <\/strong>&nbsp;to store the maximum product.<\/li><li>Run two nested loops from <strong>i = 0 <\/strong>till <strong>N &#8211; 1<\/strong> and <strong>j <\/strong>&nbsp;from <strong>i + 1 <\/strong>till <strong>N<\/strong> and for each subarray <strong>A[i\u2026.j]<\/strong>, find the product of the subarray.<\/li><li>Update and maximize <strong>result<\/strong>.<\/li><\/ul>\n\n\n\n<p><strong>Implementation of the Approach:<\/strong><\/p>\n\n\n\n<h3 id=\"c-code\"><span id=\"c-code-2\">C++ Code<\/span><\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"cpp\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">bool isOverlap(int minS, int maxE, vector&lt;int> interval)\n{\n    if (minS > interval[1] || maxE &lt; interval[0])\n    {\n        return false;\n    }\n \n    return true;\n}\n \nint maxProduct(vector&lt;int> nums) {\n  if (nums.size() == 0) return 0;\n \n  int result = nums[0];\n \n  for (int i = 0; i &lt; nums.size(); i++) {\n    int accu = 1;\n    for (int j = i; j &lt; nums.size(); j++) {\n      accu *= nums[j];\n      result = max(result, accu);\n    }\n  }\n  return result;\n}<\/pre>\n\n\n\n<h3 id=\"java-code\"><span id=\"java-code-2\">Java Code<\/span><\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"java\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">public int maxProduct(int[] nums) {\n  if (nums.length == 0) return 0;\n \n  int result = nums[0];\n \n  for (int i = 0; i &lt; nums.length; i++) {\n    int accu = 1;\n    for (int j = i; j &lt; nums.length; j++) {\n      accu *= nums[j];\n      result = Math.max(result, accu);\n    }\n  }\n \n  return result;\n}<\/pre>\n\n\n\n<h3 id=\"python-code\"><span id=\"python-code-2\">Python Code<\/span><\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"python\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">def maxProduct(nums):\n    if len(nums) == 0:\n        return 0\n \n    result = nums[0]\n \n    for i in range(len(nums)):\n        accu = 1\n        for j in range(i, len(nums)):\n            accu *= nums[j]\n            result = max(result, accu)\n \n    return result<\/pre>\n\n\n\n<p><strong>Time Complexity: <\/strong>O(N^2), where N is total size of the array<\/p>\n\n\n\n<p><strong>Space Complexity:<\/strong> O(1), as no extra space is used<\/p>\n\n\n\n<h2 id=\"approach-2-dynamic-programming\">Approach 2: Dynamic Programming<\/h2>\n\n\n\n<p>If we observe clearly, the <strong>maximum product <\/strong>will always lie either from the starting of the array or from the end of the array.<\/p>\n\n\n\n<p>To summarise, we have four possible options.<br><br>You might think, what if the <strong>maximum product<\/strong> lies somewhere in the middle of the array. Let us prove this using contradiction.<\/p>\n\n\n\n<figure class=\"wp-block-image size-large is-resized\"><img  loading=\"lazy\"  src=\"data:image\/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAAl21bKAAAAA1BMVEUAAP+KeNJXAAAAAXRSTlMAQObYZgAAAAlwSFlzAAAOxAAADsQBlSsOGwAAAApJREFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=\"  alt=\"left and right product\"  class=\"wp-image-3697 pk-lazyload\"  width=\"700\"  height=\"838\"  data-pk-sizes=\"auto\"  data-ls-sizes=\"(max-width: 700px) 100vw, 700px\"  data-pk-src=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/left-and-right-product-855x1024.png\"  data-pk-srcset=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/left-and-right-product-855x1024.png 855w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/left-and-right-product-251x300.png 251w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/left-and-right-product-768x920.png 768w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/left-and-right-product-1283x1536.png 1283w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/left-and-right-product-380x455.png 380w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/left-and-right-product-550x659.png 550w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/left-and-right-product-800x958.png 800w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/left-and-right-product-1160x1389.png 1160w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/left-and-right-product.png 1575w\" ><\/figure>\n\n\n\n<p>In the above example, it has been proved, that the maximum product<strong> <\/strong>lies either on the left end or the right end.<\/p>\n\n\n\n<p><strong>Algorithm :<\/strong><\/p>\n\n\n\n<ul><li>Initialise a variable <strong>result = A[0] <\/strong>&nbsp;to store the maximum product.<\/li><li>Initialise two variables <strong>max_so_far<\/strong> and <strong>min_so_far <\/strong>with <strong>A[0]<\/strong>, which stores the maximum and minimum product obtained so far<\/li><li>Traverse the input array and for negative element swap <strong>max_so_far <\/strong>and <strong>min_so_far<\/strong>.<\/li><li>Maximize <strong>max_so_far<\/strong> and update it with <strong>max_so_far * A[i]<\/strong><\/li><li>Minimise <strong>min_so_far<\/strong> and update it with <strong>min_so_far * A[i]<\/strong><\/li><li>Update <strong>result<\/strong> with <strong>maximum <\/strong>of <strong>max_so_far <\/strong>and <strong>min_so_far<\/strong>.<\/li><li>Return <strong>result.<\/strong><\/li><\/ul>\n\n\n\n<p><strong>Implementation of the Approach:<\/strong><\/p>\n\n\n\n<h3 id=\"c-code\">C++ Code<\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"cpp\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">vector &lt; vector &lt; int >> merge(vector &lt; vector &lt; int >> &amp; intervals) {\n  sort(intervals.begin(), intervals.end());\n \n  vector &lt; vector &lt; int >> merged;\n  for (auto interval: intervals) {\n    if (merged.empty() || merged.back()[1] &lt; interval[0]) {\n      merged.push_back(interval);\n    } else {\n      merged.back()[1] = max(merged.back()[1], interval[1]);\n    }\n  }\n  return merged;\n}<\/pre>\n\n\n\n<h3 id=\"java-code\">Java Code<\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"java\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\"> int maxProduct(vector &lt; int > nums) {\n  if (nums.size() == 0) return 0;\n \n  int max_so_far = nums[0];\n  int min_so_far = nums[0];\n  int result = max_so_far;\n \n  for (int i = 1; i &lt; nums.size(); i++) {\n    int curr = nums[i];\n    int temp_max = max(curr, Math.max(max_so_far * curr, min_so_far * curr));\n    min_so_far = min(curr, Math.min(max_so_far * curr, min_so_far * curr));\n \n    max_so_far = temp_max;\n \n    result = max(max_so_far, result);\n  }\n \n  return result;\n}<\/pre>\n\n\n\n<h3 id=\"python-code\">Python Code<\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"python\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">def maxProduct(self, nums: List[int]) -> int:\n    if len(nums) == 0:\n        return 0\n \n    max_so_far = nums[0]\n    min_so_far = nums[0]\n    result = max_so_far\n \n    for i in range(1, len(nums)):\n        curr = nums[i]\n        temp_max = max(curr, max_so_far * curr, min_so_far * curr)\n        min_so_far = min(curr, max_so_far * curr, min_so_far * curr)\n \n        max_so_far = temp_max\n \n        result = max(max_so_far, result)\n \n    return result<\/pre>\n\n\n\n<p><strong>Time Complexity:<\/strong> O(N), where N is total size of the array<\/p>\n\n\n\n<p><strong>Space Complexity:<\/strong> O(1), as no extra space is used.<\/p>\n\n\n\n<p><strong>Practice Questions:<\/strong><\/p>\n\n\n\n<p><a href=\"https:\/\/www.interviewbit.com\/problems\/max-product-subarray\/\" target=\"_blank\" rel=\"noreferrer noopener\">Max Product Subarray<\/a><\/p>\n\n\n\n<h2 id=\"faq\">FAQ<\/h2>\n\n\n\n<ul><li><strong>What if the input array has only positive integers?<\/strong><strong><br><\/strong>If the array contains just positive integers, the maximum product subarray is simply the product of all the integers.<\/li><\/ul>\n\n\n\n<ul><li><strong>What is the most efficient approach to solve the maximum product subarray?<\/strong><strong><br><\/strong>The dynamic programming approach is the most efficient approach to solve the problem. The time complexity is O(N) and space complexity is O(1).<\/li><\/ul>\n","protected":false},"excerpt":{"rendered":"Given an array A[] of N positive integers. The task is to find a non empty subarray having&hellip;\n","protected":false},"author":5,"featured_media":3700,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_daextam_enable_autolinks":"","csco_singular_sidebar":"","csco_page_header_type":"","csco_appearance_grid":"","csco_page_load_nextpost":"","csco_post_video_location":[],"csco_post_video_location_hash":"","csco_post_video_url":"","csco_post_video_bg_start_time":0,"csco_post_video_bg_end_time":0},"categories":[145],"tags":[557],"amp_enabled":true,"_links":{"self":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/3596"}],"collection":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/users\/5"}],"replies":[{"embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/comments?post=3596"}],"version-history":[{"count":4,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/3596\/revisions"}],"predecessor-version":[{"id":3740,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/3596\/revisions\/3740"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/media\/3700"}],"wp:attachment":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/media?parent=3596"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/categories?post=3596"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/tags?post=3596"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}