최대 제품 하위 배열 | 세트 2(두 개의 순회 사용)

양의 정수와 음의 정수를 모두 포함하는 배열이 주어지면 최대 곱 하위 배열의 곱을 찾습니다. 예상 시간 복잡도는 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.

우리는 이 문제의 해결책을 논의했습니다. 여기 .
이 게시물에서는 흥미로운 솔루션에 대해 논의합니다. 이 아이디어는 전체 최대 제품이 다음 두 가지의 최대값이라는 사실에 기초합니다.

왼쪽에서 오른쪽으로 순회할 때 최대 제품입니다.
오른쪽에서 왼쪽으로 순회할 때 최대 제품

예를 들어 위의 세 번째 샘플 입력 {-1 -2 -3 4}을 고려해 보세요. 순방향으로만 배열을 순회하면(출력의 일부로 -1을 고려) 최대 곱은 2가 됩니다. 배열을 역방향으로 순회하면(출력의 일부로 4를 고려) 최대 곱은 24가 됩니다. { -2 -3 4}.
한 가지 중요한 것은 0을 처리하는 것입니다. 0이 나타날 때마다 새로운 순방향(또는 역방향) 합계를 계산해야 합니다.

다음은 위의 아이디어를 구현한 것입니다.

C++

// C++ program to find maximum product subarray #include   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 negative.  // (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 negative.  // (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 negative. # (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# 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 negative.  // (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 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 negative. // (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. ?>

JavaScript

<script>  // JavaScript program to find maximum product  // subarray    // Function for maximum product  function max_product(arr n)  {    // Initialize maximum products in   // forward and backward directions  let max_fwd = Number.MIN_VALUE   max_bkd = Number.MIN_VALUE;    // Initialize current product  let 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 (let 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 (let 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  let res = Math.max(max_fwd max_bkd);    // Product should not be negative.  // (Product of an empty subarray is  // considered as 0)  return Math.max(res 0);  }    let arr = [-1 -2 -3 4];  let n = arr.length;  document.write(max_product(arr n) );   </script>

산출

시간복잡도 : O(n)
보조공간 : O(1)

위의 솔루션에는 배열을 두 번 순회해야 하는 반면 이전 솔루션 한 번의 순회만 필요합니다.