Ən böyük cəmi bitişik subarray

Çətinlik səviyyəsi Asan
Tez-tez soruşulur 24 * 7 İnnovasiya Laboratoriyaları Akkolit Amazon DE Şou Məlumat dəsti Flipkart Piyada çox yol qət eləmək mənzil.com MakeMyTrip MetLife microsoft Morgan Stanley Ola Cabs Kahin OYO Otaqları PayU Samsung Snapdeal Teradata Viza VMware Walmart Laboratoriyaları Zoho
Geyim Dinamik proqramlaşdırmaBaxılıb 82

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

Sizə bir ədəd tam ədəd verilir. Problem ifadəsi ən böyük cəmi bitişik subarrayı tapmağı xahiş edir. Bu, verilmiş massivdəki digər subarrayslar arasında ən böyük cəmi olan subarray (davamlı elementlər) tapmaqdan başqa bir şey demək deyil.

misal

arr[] = {1, -3, 4, -2, 5, -6, 2}
[2, 4]

İzahat: İndeks 2-dən indeks 4-ə qədər başlayan alt sıra, massiv içərisində ən böyük cəmi 7-yə malikdir. Hər hansı bir subarray 7-dən kiçik bir məbləğ verəcəkdir.

Ən böyük cəmi bitişik subarrayPin

 

arr[] = {1, -3, 4, -1, 4, -2, 5, -6, 2}
[2, 6]

İzahat: İndeks 2-dən indeks 6-ya qədər başlayan alt sıra, massiv içərisində ən böyük cəmi 10-a malikdir.

 

Ən böyük cəm bitişik subarray problemi üçün alqoritm

1. Set the maxValue to the minimum value an integer can hold (INT_MIN / Integer.MIN_VALUE) and maxPoint to 0.
2. Set start, end, s to 0.
3. Traverse the array starting from i=0 to i<size(length of the array).
  1. Add the maxPoint and arr[i] and update it into the maxPoint.
  2. Check if maxValue is less than maxPoint, then update the following:
    1. maxValue = maxPoint
    2. start=s
    3. end=i
  3. Check if the maxPoint is less than 0, then update
    1. maxPoint=0
    2. s=i+1
4. Print ‘start’ and ‘end’ as an index and the maxValue as the largest sum.

Izahat

Biz verdik array tam ədədi. Ən böyük cəmi bitişik subarrayı tapmağı xahiş etdik. Tərkibində mənfi və müsbət tam ədədlər də ola bilər. Bütün bu işlərin öhdəsindən gəlməliyik. Bunun üçün serialı yalnız bir dəfə keçəcəyik və bu səbəbdən də mürəkkəblik vaxtına sahibdir O (n). Xətti zaman mürəkkəbliyində maksimum bitişik subarray cəmini tapacağıq.

Kimi bəzi dəyərlər qurun maksimum dəyər Bir Tamsayı tuta biləcəyi minimum dəyərə, maxPoint 0-a və Başlamaq, sons 0-a qədər. Dizini uzunluğa qədər keçməyə başlayın n. Cari array elementini cəmi maxPoint-ə əlavə edin. Hər zaman dəyəri olan maxPoint-də saxlayın i loopda artımlar, bu əməliyyatı edirik. Artıq dəyərini təyin etdik maksimum dəyər bir Tamsayı minimum dəyərinə və maxValue-nun maxPoint-dən az olub olmadığını yoxlayın. Bu doğrudursa, maxValue dəyərini maxPoint-dən yeniləyəcəyik, s-ə başlayın. Bu başlanğıc dəyişən bitişik alt dizinin başlanğıc aralığının dəyərini təyin edəcək və i (loop dəyişən) ilə yenilədiyimiz bir sonumuz var.

İndi yoxlayacağıq maxPoint 0-dan azdırsa, indiyə qədər sıra dəyərlərinin əlavə edilməsi mənfi deməkdir. Sonra yenidən maxPoint dəyərini 0-a, s-i isə i + 1-ə yeniləyirik. Bu s başlanğıc aralığının dəyərini təyin etməkdə bizə yenidən kömək edəcək və ən böyük cəm subarrayını tapmaqda bizə kömək edəcəkdir. Bu maxPoint sıfıra başlanacaq, çünki ən böyük cəmi tapmaq məcburiyyətindəyik və sonra başlanğıc və sonun dəyərini tələb olunan ən böyük cəmi alt serialın başlanğıc və bitmə göstəricisi olaraq çap edəcəyik. Bu yanaşmadan istifadə etsək, bir keçiddə ən böyük cəmi bitişik subarray tapa bilərik.

 

Ən böyük cəmi bitişik subarray problemi üçün kod

C ++ kodu

#include<bits/stdc++.h>
using namespace std;

// This Function prints the Largest Sum Contiguous Subarray
void getLargestSumContiguousSubarray(int arr[], int size)
{
    // initialising variables with starting values
    int maxValue = INT_MIN;
    int  maxPoint = 0;
    int start =0, end = 0, s=0;

    for (int i=0; i< size; i++ )
    {
        maxPoint += arr[i];

        if (maxValue < maxPoint)
        {
            maxValue = maxPoint;
            start = s;
            end = i;
        }

        if (maxPoint < 0)
        {
            maxPoint = 0;
            s = i + 1;
        }
    }
    cout << "Sub-Array starting from "<< start<< " to "<< end<< " has a largest sum of " <<maxValue;
}
int main()
{
    int arr[] = {1, -3, 4, -2, 5, -6, 2};
    int n = sizeof(arr)/sizeof(arr[0]);
    getLargestSumContiguousSubarray(arr, n);
    return 0;
}
Sub-Array starting from 2 to 4 has a largest sum of 7

 

Java kodu

class LargestSumSubArray
{
    // This Function prints Largest Sum Contiguous Subarray
    public static void getLargestSumContiguousSubarray(int arr[], int size)
    {
        // initialising variables with starting values
        int maxValue = Integer.MIN_VALUE;
        int  maxPoint = 0;
        int start =0, end = 0, s=0;

        for (int i=0; i< size; i++ )
        {
            maxPoint += arr[i];

            if (maxValue < maxPoint)
            {
                maxValue = maxPoint;
                start = s;
                end = i;
            }

            if (maxPoint < 0)
            {
                maxPoint = 0;
                s = i + 1;
            }
        }
        System.out.println("Sub-Array starting from "+ start + " to "+ end + " has a largest sum of " + maxValue);
    }
    public static void main(String [] args)
    {
        int arr[] = {1, -3, 4, -2, 5, -6, 2};
        int n = arr.length;
        getLargestSumContiguousSubarray(arr, n);
    }
}
Sub-Array starting from 2 to 4 has a largest sum of 7

Mürəkkəblik təhlili

Zamanın mürəkkəbliyi

N ölçülü giriş massivi üzərində tək bir döngə işlədirdiyimiz üçün. Beləliklə, ən böyük cəmi bitişik subarray üçün alqoritm xətti zaman mürəkkəbliyinə malikdir. O (n) hara "N" massivdəki elementlərin sayıdır.

Kosmik Mürəkkəblik

Tam ədədlərin saxlanması üçün tək bir 1D giriş massivindən istifadə etdik. Beləliklə, ən böyük cəmi bitişik subarray probleminə xətti bir kosmik mürəkkəblik vermək. O (n) hara "N" massivdəki elementlərin sayıdır.

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