Maksimum məhsul subarray

Maksimum məhsul subarray problemində bir array tam ədədən, ən böyük məhsula sahib olan ən azı bir elementlə bitişik alt serialı tapın.

misal

Arr = [0, -1, 0, 1, 2, -3]

Maksimum məhsul = 2

Arr = [- 1, -1, -1]

Maksimum məhsul = -1

Arr = [0, -1, 0, -2, 0]

Maksimum məhsul = 0

Array Üçün Yalnız Müsbət Dəyərlər var

Dizidə yalnız mənfi olmayan tam ədədlər olduqda əvvəlcə bu problemi həll edək.

Bu vəziyyətdə alt bir sıra sıfır içermirsə, müsbət bir məhsula sahib ola bilərik. Buna görə cavab, subarrays məhsullarını maksimum sıfır olmadan edəcəkdir.

Nümunə götürək:

Pin

Maksimum məhsul subarray üçün C ++ proqramı

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n=7;
    int arr[]={10, 1, 0, 3, 9, 2, 1};
    int ans=0,curr_product=0;
    for(int i=0;i<n;i++){
        if(arr[i]==0){
            ans=max(ans,curr_product);
            curr_product=0;
        }
        else{
            curr_product=max(arr[i]*curr_product,arr[i]);
        }
    }
    ans=max(ans,curr_product);
    cout<<ans;
}

54

Array Üçün mənfi dəyərlər də var

İndi, sıra da mənfi dəyərlər içərsə nə edər?

Bu vəziyyətdə (i-1) -ci indekslə bitən maksimum məhsulun optimal cavab vermək üçün arr [i] ilə çoxalmasını təmin edə bilmərik.

Misal üçün:

arr = [1-2 -3]

Maksimum məhsul:

• i = 0 1 olarsa
• i = 1 1-dir
• i = 2 6-dır (-2 * -3)

Bu problemi həll etmək üçün sadəcə iki sıra yarada bilərik:

1. İth indeksində bitən maksimum məhsulu saxlamaq üçün biri.
2. Digərləri ith indeksində bitən minimum məhsulu saxlamaq üçün.

İndi serialın hər mövqeyində üç seçiminiz var:

1. Cari elementi indiyə qədər hesablanmış maksimum məhsulla vurun.
2. Cari elementi indiyə qədər hesablanmış minimum məhsulla vurun.
3. Maksimum məhsul alt üçün başlanğıc mövqeyi olaraq cari elementi götürün
   serial.

Maksimum məhsul subarray üçün C ++ proqramı

#include<bits/stdc++.h>
using namespace std;
int maxProduct(int n,int a[]) {
    int mini[n];       // minimum product ending with ith index
    int maxi[n];       // maximum product ending with ith index
    
    mini[0]=a[0];
    maxi[0]=a[0];
    
    int ans = a[0];
    for(int i=1;i<n;i++) 
    {
        if(a[i]>0)
        {
            maxi[i] = max(maxi[i-1]*a[i], a[i]);
            mini[i] = min(mini[i-1]*a[i], a[i]);
        }
        else
        {
            maxi[i] = max(mini[i-1]*a[i], a[i]);
            mini[i] = min(maxi[i-1]*a[i], a[i]);
        }
        ans = max(ans, maxi[i]);
    }

    return ans;
}
int main(){
    int n;
    cin>>n;
    int a[n];
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    int ans =maxProduct(n,a);
    cout<<"Maximum product of a subarray in the given array is "<<ans;
}

5
-2 7 5 -2 1

Maximum product of a subarray in the given array is 140

JAVA Proqramı

import java.util.Scanner;

class Main{ 
static int maxProduct(int a[], int n) 
{ 
  int mini[] = new int[n];       // minimum product ending with ith index
    int maxi[] = new int[n];       // maximum product ending with ith index
    
    mini[0]=a[0];
    maxi[0]=a[0];
    
    int ans = a[0];
    for(int i=1;i<n;i++) 
    {
        if(a[i]>0)
        {
            maxi[i] = Math.max(maxi[i-1]*a[i], a[i]);
            mini[i] = Math.min(mini[i-1]*a[i], a[i]);
        }
        else
        {
            maxi[i] = Math.max(mini[i-1]*a[i], a[i]);
            mini[i] = Math.min(maxi[i-1]*a[i], a[i]);
        }
        ans = Math.max(ans, maxi[i]);
    }

    return ans;
} 

  public static void main(String[] args) { 
  Scanner sc = new Scanner(System.in);
    int n;
    n = sc.nextInt();	
  int a[] = new int[n]; 
  for(int i=0;i<n;i++){
      a[i] = sc.nextInt();
  }
    System.out.println("Maximum product of a subarray in the given array is "+maxProduct(a, n)); 
  } 
}

6
4 6 -2 -9 -3 1

Maximum product of a subarray in the given array is 432

Maksimum məhsul subarray üçün mürəkkəblik analizi

Zaman Mürəkkəbliyi: O (n) burada n yalnız bir sıra keçid tələb olunduğundan bir sıra uzunluğu.

Kosmik Mürəkkəblik: O (n) çünki hər mövqe üçün minimum və maksimum məhsulu saxlamaq üçün iki sıra istifadə edirik.

References