{"id":2046,"date":"2024-03-09T13:00:00","date_gmt":"2024-03-09T13:00:00","guid":{"rendered":"https:\/\/favtutor.com\/articles\/?p=2046"},"modified":"2024-03-11T07:51:24","modified_gmt":"2024-03-11T07:51:24","slug":"maximum-product-subarray-problem","status":"publish","type":"post","link":"https:\/\/favtutor.com\/articles\/maximum-product-subarray-problem\/","title":{"rendered":"Find Maximum Product Subarray (C++, Java, Python)"},"content":{"rendered":"\n

A subarray is a continuous sequence of an array and a lot of algorithms like Kadane\u2019s algorithm<\/a>, sliding window<\/a>, etc. help to determine the maximum sum of the subarray or to find the sum of the maximum k-length subarray, etc. In this article, we will discuss the Maximum product Subarray problem with implementation in C++, Java, and Python.<\/p>\n\n\n\n

Maximum Product Subarray Problem<\/strong><\/h2>\n\n\n\n

In the Maximum Product Subarray problem, we are given an array and we have to find a subarray such that the product of all the elements in that subarray will be the largest.<\/strong><\/p>\n\n\n\n

For example:\u00a0 <\/p>\n\n\n\n

INPUT:<\/strong>\u00a0 -1, 2, 3, -2<\/p>\n\n\n\n

OUTPUT: <\/strong>\u00a0 12\u00a0 ( -1 * 2 * 3 * -2)\u00a0<\/p>\n\n\n\n

INPUT:\u00a0 \u00a0<\/strong> \u00a0 1, 2, 3,- 2<\/p>\n\n\n\n

OUTPUT<\/strong>: \u00a0 6\u00a0 ( 1 * 2 * 3)\u00a0<\/p>\n\n\n

\n
\"Example<\/figure>\n<\/div>\n\n\n

The basic or naive approach is to find all the subarrays and then find which among them have the largest product. Let\u2019s see step by step solution.<\/p>\n\n\n\n

    \n
  1. Create a loop of size n<\/li>\n\n\n\n
  2. Create another loop starting from the index of the previous loop.<\/li>\n\n\n\n
  3. Now find the product of the given subarray and compare it with the max value.<\/li>\n\n\n\n
  4. If it is greater than max variable update max to this new product.<\/li>\n\n\n\n
  5. Return the max element.<\/li>\n<\/ol>\n\n\n\n

    The time complexity for the above process is O(n*n). Where n is the size of the array. We are iterating two loops to generate all the subarrays. The space complexity for the above code is O(1) as we are not using any extra space.\u00a0<\/p>\n\n\n\n

    Optimized Approach for Maximum Product Subarray<\/strong><\/h2>\n\n\n\n

    In the above approach, the time complexity is huge is can be reduced if we use the concept of Kadane\u2019s algorithm. In this, we will first traverse the array from the left side and find its maximum value then traverse the array from the right side and find its maximum value. Return the maximum value among both of them. <\/p>\n\n\n\n

    We are doing this as we know if we have a negative value the maximum product either lies on the left side or right. But if we have two negative values, the product will be positive only.<\/p>\n\n\n\n

    Let\u2019s understand this step by step:<\/p>\n\n\n\n

    \"Optimized<\/figure>\n\n\n\n