Maksimum dairəvi subarray cəmi

Çətinlik səviyyəsi Mühit
Tez-tez soruşulur Amazon Facebook LinkedIn İki Sigma Über
GeyimBaxılıb 530

Sistem dizaynı ilə bağlı müsahibə sualları o qədər açıq ola bilər ki, düzgün hazırlaşmağı bilmək çox çətindir. İndi satın aldıqdan sonra Amazon, Microsoft və Adobe-nin dizayn dövrlərini sındıra bilirəm Bu kitabı. Gündəlik bir yenidən nəzərdən keçirin dizayn sualı və söz verirəm ki, dizayn dövrünü sındıra bilərsiniz.

Problem bəyanat

Maksimum dairəvi subarray cəmi problemində bir array dairə şəklində düzülmüş tam ədədlər, dairəvi massivdə ardıcıl sayların maksimum cəmini tapın.

misal

Input

arr [] = {13, -17, 11, 9, -4, 12, -1}

Buraxılış

40

Izahat

Burada cəmi = 11 + 9 + -4 + 12 + -1 + 13

Input

arr [] = {7, 9, -11, -2, 2, 7, -1, 6}

Buraxılış

30

Izahat

Burada cəmi = 2 + 7 + -1 + 6+ 7 + 9

Input

arr [] = {-17, -2, 1, -10, 2, 3, 7, 9}

Buraxılış

21

Izahat

Burada cəmi = 2 + 3 + 7 + 9

Maksimum dairəvi subarray cəmi üçün alqoritm

Maksimum dairəvi subarray cəmi problemində iki şərtimiz var. Birinci şərt bütün elementlərin bitişik alt bölmədə olmasıdır. İkinci şərt isə bəzi elementlərin massivin başlanğıcından, sonlarından isə bəzi elementlər olmasıdır. Daha yaxşı başa düşmək üçün aşağıdakı alqoritmə baxın -

1) Maksimum məbləğə qatqı təmin edən elementlər elə bir şəkildə yerləşdirilib ki, orada heç bir bükülmə olmasın. Nümunədəki kimi (c)

2) Maksimum məbləğə qatqı təmin edən elementlər sarmağın olduğu yerdə yerləşdirilmişdir. Nümunədəki kimi (a, b).

3) İş 1 üçün standartı istifadə edirik Kadane alqoritmi maksimum subray cəmi tapmaq.

4) 2-ci vəziyyət üçün sarmağı qeyri-sarğı ilə dəyişdiririk.

  • Bütün elementlərin cəmini massivdə saxlayırıq.
  • Cəmi əlavə edərkən bütün elementlərin işarəsini dəyişdirin.
  • Ters işarələri olan yeni sıra üçün yenidən bu yeni massivə kadane alqoritmi tətbiq edin.
  • Cəmi cəmi yeni kadane cəmi ilə əlavə edin.
  • Bu cəmi ilk kadane cəmi ilə müqayisə edin (işarələri tərs etməzdən əvvəl) aralarında maksimum qayıt.

Həyata keçirilməsi

Maksimum Dairəvi Subarray Cəmi üçün C ++ Proqramı

#include <bits/stdc++.h>
using namespace std;
// Standard Kadane's algorithm to find maximum subarray sum
int kadane(int array[], int n)
{
    int max_so_far = 0, max_ending_here = 0;
    for (int i = 0; i < n; i++)
    {
        max_ending_here = max_ending_here + array[i];
        if (max_ending_here < 0)
            max_ending_here = 0;
        if (max_so_far < max_ending_here)
            max_so_far = max_ending_here;
    }
    return max_so_far;
}
 
//function to find maximum circular subarray sum
int MaxSumCircular(int array[], int n)
{
    //Max subarray sum in the given array
    int kadane_sum = kadane(array, n);
    //wrap_sum is sum of all elements in the array
    int wrap_sum = 0;
    //find sum of all elements in the array
    //invert signs of all elements in the array
    for (int i=0; i<n; i++)
    {
        wrap_sum += array[i]; 
        array[i] = -array[i];
    }
    //update wrap_sum by add to new Max subarray sum
    wrap_sum = wrap_sum + kadane(array, n);
    //Return the maximum of them
    if(wrap_sum > kadane_sum)
    {
      return wrap_sum;
    }
    else
    {
      return kadane_sum;
    }
}
  
//Main function
int main()
{
    int input_array[] = {7, 9, -11, -2, 2, 7, -1, 6};
    int size = sizeof(input_array)/sizeof(int);
    cout<<"Maximum circular subarray sum: "<<MaxSumCircular(input_array,size)<<endl;
    return 0;
}

Maksimum Dairəvi Subarray Cəmi üçün Java Proqramı

import java.util.Arrays;
import java.util.Scanner;
class sum
{
    public static int kadane(int array[], int n)
    {
        int max_so_far = 0, max_ending_here = 0;
        for (int i = 0; i < n; i++)
        {
            max_ending_here = max_ending_here + array[i];
            if (max_ending_here < 0)
                max_ending_here = 0;
            if (max_so_far < max_ending_here)
                max_so_far = max_ending_here;
        }
        return max_so_far;
    }
    public static int MaxSumCircular(int array[], int n)
    {
        //Max subarray sum in the given array
        int kadane_sum = kadane(array, n);
        //wrap_sum is sum of all elements in the array
        int wrap_sum = 0;
        //find sum of all elements in the array
        //invert signs of all elements in the array
        for (int i=0; i<n; i++)
        {
            wrap_sum += array[i]; 
            array[i] = -array[i];
        }
        //update wrap_sum by add to new Max subarray sum
        wrap_sum = wrap_sum + kadane(array, n);
        //Return the maximum of them
        if(wrap_sum > kadane_sum)
        {
          return wrap_sum;
        }
        else
        {
          return kadane_sum;
        }
    } 
    public static void main(String[] args)  
    { 
        Scanner sr = new Scanner(System.in);
        int n = sr.nextInt();
        int arr[] = new int[n];
        for(int i=0;i<n;i++)
        {
            arr[i] = sr.nextInt();
        } 
        int ans = MaxSumCircular(arr,n);
        System.out.println("Maximum circular subarray sum: " + ans);
    } 
}
8
7 9 -11 -2 2 7 -1 6
Maximum circular subarray sum: 30

Mürəkkəblik təhlili

Zamanın mürəkkəbliyi

O (N) burada N - verilən massivdə mövcud olan elementlərin sayı. Burada bizi xətti zaman mürəkkəbliyinə aparan kadane alqoritmindən istifadə edirik.

Kosmik Mürəkkəblik

O (1) çünki nəticəni az dəyişkən istifadə edərək hesablayırıq. Burada optimal kosmik kadane alqoritmindən istifadə edirik.

References

Crack Sistemi Dizayn Müsahibələri
Translate »