算法：找出最大乘积子数组|s2（使用两次遍历）

2021年3月12日13:52:45 发表评论 651 次浏览

本文概述

给定一个同时包含正整数和负整数的数组, 请最大乘积子数组。预期的时间复杂度为O(n), 并且只能使用O(1)的额外空间。

例子 ：

Input: arr[] = {6, -3, -10, 0, 2}
Output:   180  // The subarray is {6, -3, -10}

Input: arr[] = {-1, -3, -10, 0, 60}
Output:   60  // The subarray is {60}

Input: arr[] = {-1, -2, -3, 4}
Output:   24  // The subarray is {-2, -3, 4}

Input: arr[] = {-10}
Output:   0  // An empty array is also subarray
             // and product of empty subarray is
             // considered as 0.

推荐：请尝试以下方法{IDE}首先, 在继续解决方案之前。

我们已经讨论了此问题的解决方案

这里

.

在这篇文章中, 讨论了一个有趣的解决方案。该想法基于以下事实：总体最大乘积是以下两个的最大值：

  1. 从左到右遍历的最大乘积。
  2. 从右到左遍历的最大乘积

例如, 考虑上面的第三个样本输入{-1, -2, -3, 4}。如果仅向前移动数组(将-1作为输出的一部分), 则最大乘积将为2。如果我们向后移动数组(将4作为输出的一部分), 则最大乘积将为24。 {-2, -3, 4}。

重要的一件事是处理0。每当我们看到0时, 就需要计算新的正向(或反向)和。

下面是上述想法的实现：

C ++

// C++ program to find maximum product subarray
#include<bits/stdc++.h>
using namespace std;
  
// Function for maximum product
int max_product( int arr[], int n)
{
     // Initialize maximum products in forward and
     // backward directions
     int max_fwd = INT_MIN, max_bkd = INT_MIN;
  
     // Initialize current product
     int max_till_now = 1;
  
     //check if zero is present in an array or not
     bool isZero= false ;
      
     // max_fwd for maximum contiguous product in
     // forward direction
     // max_bkd for maximum contiguous product in
     // backward direction
     // iterating within forward direction in array
     for ( int i=0; i<n; i++)
     {
         // if arr[i]==0, it is breaking condition
         // for contiguous subarray
         max_till_now = max_till_now*arr[i];
         if (max_till_now == 0)
         {   
              isZero= true ;
              max_till_now = 1;
             continue ;
         }
         if (max_fwd < max_till_now) // update max_fwd
             max_fwd = max_till_now;
     }
  
      max_till_now = 1;
  
     // iterating within backward direction in array
     for ( int i=n-1; i>=0; i--)
     {
         max_till_now = max_till_now * arr[i];
         if (max_till_now == 0)
         {
             isZero= true ;
             max_till_now = 1;
             continue ;
         }
  
         // update max_bkd
         if (max_bkd < max_till_now)
             max_bkd = max_till_now;
     }
  
     // return max of max_fwd and max_bkd
     int res =  max(max_fwd, max_bkd);
  
     // Product should not be nagative.
     // (Product of an empty subarray is
     // considered as 0)
     if (isZero)
     return max(res, 0);
  
     return res;
}
  
// Driver Program to test above function
int main()
{
     int arr[] = {-1, -2, -3, 4};
     int n = sizeof (arr)/ sizeof (arr[0]);
     cout << max_product(arr, n) << endl;
     return 0;
}

Java

–

// Java program to find
// maximum product subarray
import java.io.*;
  
class GFG 
{
  
// Function for maximum product
static int max_product( int arr[], int n)
{
     // Initialize maximum products in 
     // forward and backward directions
     int max_fwd = Integer.MIN_VALUE, max_bkd = Integer.MIN_VALUE;
  
     //check if zero is present in an array or not
     boolean isZero= false ;
  
     // Initialize current product
     int max_till_now = 1 ;
  
     // max_fwd for maximum contiguous 
     // product in forward direction
     // max_bkd for maximum contiguous 
     // product in backward direction
     // iterating within forward 
     // direction in array
     for ( int i = 0 ; i < n; i++)
     {
         // if arr[i]==0, it is breaking 
         // condition for contiguous subarray
         max_till_now = max_till_now * arr[i];
         if (max_till_now == 0 )
         {
             isZero= true ;
             max_till_now = 1 ;
             continue ;
         }
          
         // update max_fwd
         if (max_fwd < max_till_now) 
             max_fwd = max_till_now;
     }
  
     max_till_now = 1 ;
  
     // iterating within backward 
     // direction in array
     for ( int i = n - 1 ; i >= 0 ; i--)
     {
         max_till_now = max_till_now * arr[i];
         if (max_till_now == 0 )
         {
             isZero= true ;
             max_till_now = 1 ;
             continue ;
         }
  
         // update max_bkd
         if (max_bkd < max_till_now)
             max_bkd = max_till_now;
     }
  
     // return max of max_fwd and max_bkd
     int res = Math. max(max_fwd, max_bkd);
  
     // Product should not be nagative.
     // (Product of an empty subarray is
     // considered as 0)
      if (isZero)
     return Math.max(res, 0 );
      
     return res;
}
  
// Driver Code
public static void main (String[] args) 
{
     int arr[] = {- 1 , - 2 , - 3 , 4 };
     int n = arr.length;
     System.out.println( max_product(arr, n) );
}
}
  
// This code is contributed by anuj_67.

Python3

# Python3 program to find
# maximum product subarray 
import sys
  
# Function for maximum product 
def max_product(arr, n):
  
     # Initialize maximum products 
     # in forward and backward directions 
     max_fwd = - sys.maxsize - 1
     max_bkd = - sys.maxsize - 1
      
     #check if zero is present in an array or not
     isZero = False ;
  
     # Initialize current product 
     max_till_now = 1
  
     # max_fwd for maximum contiguous
     # product in forward direction 
     # max_bkd for maximum contiguous 
     # product in backward direction 
     # iterating within forward 
     # direction in array 
     for i in range (n): 
      
         # if arr[i]==0, it is breaking 
         # condition for contiguous subarray 
         max_till_now = max_till_now * arr[i]
         if (max_till_now = = 0 ):
             isZero = True
             max_till_now = 1 ; 
             continue
          
         if (max_fwd < max_till_now): #update max_fwd 
             max_fwd = max_till_now 
      
     max_till_now = 1
  
     # iterating within backward
     # direction in array 
     for i in range (n - 1 , - 1 , - 1 ):
         max_till_now = max_till_now * arr[i] 
          
         if (max_till_now = = 0 ): 
             isZero = True
             max_till_now = 1
             continue
  
         # update max_bkd 
         if (max_bkd < max_till_now) : 
             max_bkd = max_till_now 
  
     # return max of max_fwd and max_bkd 
     res = max (max_fwd, max_bkd) 
  
     # Product should not be nagative. 
     # (Product of an empty subarray is 
     # considered as 0) 
     if isZero = = True
     return max (res, 0 )
  
     return res 
  
# Driver Code
arr = [ - 1 , - 2 , - 3 , 4 ] 
n = len (arr) 
print (max_product(arr, n))
  
# This code is contributed 
# by Yatin Gupta

C#

// C# program to find maximum product
// subarray
using System; 
  
class GFG {
  
     // Function for maximum product
     static int max_product( int []arr, int n)
     {
          
         // Initialize maximum products in 
         // forward and backward directions
         int max_fwd = int .MinValue, max_bkd = int .MinValue;
      
         // Initialize current product
         int max_till_now = 1;
      
         // max_fwd for maximum contiguous 
         // product in forward direction
         // max_bkd for maximum contiguous 
         // product in backward direction
         // iterating within forward 
         // direction in array
         for ( int i = 0; i < n; i++)
         {
              
             // if arr[i]==0, it is breaking 
             // condition for contiguous subarray
             max_till_now = max_till_now * arr[i];
              
             if (max_till_now == 0)
             {
                 max_till_now = 1;
                 continue ;
             }
              
             // update max_fwd
             if (max_fwd < max_till_now) 
                 max_fwd = max_till_now;
         }
      
         max_till_now = 1;
      
         // iterating within backward 
         // direction in array
         for ( int i = n - 1; i >= 0; i--)
         {
             max_till_now = max_till_now * arr[i];
             if (max_till_now == 0)
             {
                 max_till_now = 1;
                 continue ;
             }
      
             // update max_bkd
             if (max_bkd < max_till_now)
                 max_bkd = max_till_now;
         }
      
         // return max of max_fwd and max_bkd
         int res = Math. Max(max_fwd, max_bkd);
      
         // Product should not be nagative.
         // (Product of an empty subarray is
         // considered as 0)
         return Math.Max(res, 0);
     }
      
     // Driver Code
     public static void Main () 
     {
         int []arr = {-1, -2, -3, 4};
         int n = arr.Length;
          
         Console.Write( max_product(arr, n) );
     }
}
  
// This code is contributed by nitin mittal.

的PHP

<?php
// PHP program to find maximum 
// product subarray
  
// Function for maximum product
function max_product( $arr , $n )
{
      
     // Initialize maximum products
     // in forward and backward
     // directions
     $max_fwd = PHP_INT_MIN; 
     $max_bkd = PHP_INT_MIN;
  
     // Initialize current product
     $max_till_now = 1;
  
     // max_fwd for maximum contiguous 
     // product in forward direction
     // max_bkd for maximum contiguous
     // product in backward direction
     // iterating within forward direction
     // in array
     for ( $i = 0; $i < $n ; $i ++)
     {
          
         // if arr[i]==0, it is
         // breaking condition
         // for contiguous subarray
         $max_till_now = $max_till_now * $arr [ $i ];
         if ( $max_till_now == 0)
         {
             $max_till_now = 1;
             continue ;
         }
          
         // update max_fwd
         if ( $max_fwd < $max_till_now ) 
             $max_fwd = $max_till_now ;
     }
  
     $max_till_now = 1;
  
     // iterating within backward 
     // direction in array
     for ( $i = $n - 1; $i >= 0; $i --)
     {
         $max_till_now = $max_till_now * $arr [ $i ];
         if ( $max_till_now == 0)
         {
             $max_till_now = 1;
             continue ;
         }
  
         // update max_bkd
         if ( $max_bkd < $max_till_now )
             $max_bkd = $max_till_now ;
     }
  
     // return max of max_fwd
     // and max_bkd
     $res = max( $max_fwd , $max_bkd );
  
     // Product should not be nagative.
     // (Product of an empty subarray is
     // considered as 0)
     return max( $res , 0);
}
  
     // Driver Code
     $arr = array (-1, -2, -3, 4);
     $n = count ( $arr );
     echo max_product( $arr , $n );
  
// This code is contributed by anuj_67.
?>

输出：

24

时间复杂度：

上)

辅助空间：

O(1)

请注意, 上述解决方案需要两次遍历数组, 而先前的解决方案只需要一个遍历。

如果发现任何不正确的地方, 或者想分享有关上述主题的更多信息, 请写评论。

木子山

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: