Maksimum məhsul subarray II

Çətinlik səviyyəsi Mühit
Tez-tez soruşulur Amazon alma Bloomberg Facebook google LinkedIn microsoft
Geyim Dinamik proqramlaşdırmaBaxılıb 582

Problem bəyanat

“Maksimum məhsul subarray II” problemində bir array müsbət, mənfi tamsayılardan və eyni zamanda sıfırdan ibarətdir. Subarrayın maksimum məhsulunu tapmaq lazımdır.

Giriş Formatı

Bir tam ədədi olan ilk sətir.

N boşluqla ayrılmış tam ədədi olan ikinci sətir.

Çıxış formatı

Subarrayın maksimum məhsulunu göstərən bir tam ədədi ehtiva edən tək sətir.

Məhdudiyyətlər

  • 1 <= N <= 10 ^ 5
  • -100 <= A [i] <= 100

misal

5
3 -6 -1 0 4
18

Explanation: Subarray [3, -6, -1] maksimum məhsul əldə edir.

Maksimum məhsul subarray II üçün alqoritm

Bizə bir tam sıra verilir və ən böyük məhsula sahib olan davamlı subrayı tapmalıyıq. Tam həll yolu tapmadan əvvəl problemin ən sadə versiyasını görək -

  • Massiv yalnız müsbət rəqəmlərdən ibarətdirsə - Çözüm massivin bütün elementlərinin məhsulu olacaqdır.
  • Dizidə mənfi olmayan rəqəmlər varsa (müsbət və sıfır) - Dizini keçirik və sıfırla qarşılaşdığımız zaman çalışan_ məhsulu hesablayırıq, onda işləyən_ məhsul məhsulu sıfır olacaqdır, buna görə hər işləmə məhsulu cari saydan az olduqda, bu mövqedən yeni bir subarray başlanğıcını düşünürük. Qarşılaşdığımız maksimum məhsulu saxlamaq üçün bir dəyişənə ehtiyacımız var.

Int mx_product = sıra [0]

Int running_product = sıra [0]

üçün (int i = 1; i

running_product = max (running_product * array [i], array [i]);

mx_product = max (mx_product, çalışan_product)

}

  • İndi mənfi rəqəmləri də nəzərdən keçirin - Bir sıra düşünün                                                                                         İkinci elementdə olduğumuzda çalışan məhsulumuz -12 olur. Ancaq 3-cü vəziyyətdə 60 olur. Mənfi rəqəmlərlə qarşılaşdığımızda məhsulumuzun işarəsi dəyişir. Məhsul həqiqətən kiçik olur və sonra işarələrin dəyişdirilməsində böyük olur. Beləliklə çalışan_prod_max və running_prod_min iki işləyən məhsul dəyişənini götürürük. Neqativ bir rəqəmlə qarşılaşdığımız zaman çalışan_prod_max və running_prod_min-i dəyişdiririk Əgər (a <= b)

    Hər ikisini -1-ə vursaq

    Sonra -a> = b

    running_prod_max işləyən məhsulu saxlayır və işləyən məhsul run_prod_max-dan maksimum olduqda yeniləyir, işləyən məhsul running_prod_min-dən az olduqda, çalışan_prod_min-i yeniləyirik.

    Maksimum məhsulu saxlamaq üçün max_prod dəyişənini də alırıq.

Həyata keçirilməsi

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

#include <iostream>
using namespace std;

int max_prod_subarray(int a[],int n){
  if(n==0) return 0;
  
  int max_prod = a[0], running_prod_max = a[0], running_prod_min = a[0];
  
  for(int i=1;i<n;i++){
    if(a[i]<0){
      swap(running_prod_max,running_prod_min);
    }
    running_prod_max = max(running_prod_max*a[i],a[i]);
    running_prod_min = min(running_prod_min*a[i],a[i]);
    
    max_prod = max(max_prod,running_prod_max);
  }
  
  return max_prod;
  
}

int main() {
  int n;
  cin>>n;
  int arr[n];
  for(int i=0;i<n;i++) cin>>arr[i];
  int max_prod = max_prod_subarray(arr,n);
  cout<<max_prod<<endl;
  return 0;
}

Maksimum məhsul subarray II üçün Java Proqramı

import java.util.*;
import java.lang.*;
import java.io.*;

public class Main
{
  public static void main (String[] args) throws java.lang.Exception
  {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    int[] arr = new int[n];
    for(int i=0;i<n;i++){
            arr[i]=sc.nextInt();
        }
        int max_prod = max_prod_subarray(arr,n);
        System.out.println(max_prod);
  }
  
  public static int max_prod_subarray(int[] a,int n){
        if(n==0){
            return 0;
        }
        int max_prod = a[0], running_prod_max = a[0], running_prod_min = a[0];
 
    for(int i=1;i<n;i++){
      if(a[i]<0){
        swap(running_prod_max,running_prod_min);
      }
      running_prod_max = Math.max(running_prod_max*a[i],a[i]);
      running_prod_min = Math.min(running_prod_min*a[i],a[i]);
   
      max_prod = Math.max(max_prod,running_prod_max);
    }
    
    return max_prod;
    }
    
    public static void swap(int a, int b) 
    { 
        int temp = a; 
        a = b; 
        b = temp; 
    } 

}
4
1 -2 -3 4
24

Maksimum Məhsul Subarray II üçün Mürəkkəblik Analizi

Zamanın mürəkkəbliyi

O (n) hara n verilmiş massivin ölçüsüdür. Burada serialı yalnız bir dəfə keçirik və cavabı yalnız bir keçidlə alırıq.

Kosmik Mürəkkəblik

O (1) çünki burada heç bir köməkçi yer yaratmırıq.

Translate »