Maksimum cəmi olan subarray ölçüsü

Çətinlik səviyyəsi Asan
Tez-tez soruşulur Coursera Boz Portağal UHG Optum Xome
Geyim Dinamik proqramlaşdırmaBaxılıb 395

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ə verilir array tam ədədi. Verilən massivdə həm müsbət, həm də mənfi rəqəmlər ola bilər. Maksimum cəm ​​ilə subarrayın ölçüsünü öyrənin.

misal

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

İzahat: 2 -1 + 4 + 3 = 8 maksimum 4 uzunluğunun cəmidir


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

İzahat: 1 + 2 = 3 maksimum 2 uzunluğunun cəmidir

Alqoritm

1. Set the maxVal to the minimum value of an integer and maxPoint to 0, start, end, and s to 0.
2. Starting from i=0 to i<size(length of the array).
  1. Sum up the value of maximumPoint and arr[i] and store into the maximumPoint.
  2. Check if maxVal is less than maxPoint, then update the following:
    maxVal = maxPoint
    start=s
    nd=i
  3. Check if the maximumPoint is less than 0, then update
    maximumPoint=0
    s=i+1
3. Return the value (end – start + 1).

Maksimum cəm ​​ilə subarray ölçüsünün hesablanması üçün izah

Bir sıra tam ədədlər verilmişdir. Bizim vəzifəmiz uzunluğunu tapmaqdır maksimum cəmi olan subarray. Mənfi və müsbət tam ədədi də ehtiva edə bilər. Gedirik keçmək sərgi yalnız bir dəfə və sonrasında O (n) zaman kompleksliyinə sahibdir. Tapın ən böyük xətti zaman mürəkkəbliyindəki alt dəyər cəmi.

Kimi dəyişənin müəyyən dəyərlərini qurun maksimum dəyər anın minimum dəyərinə Tam, maxPoint 0-a və Başlamaq, son s 0-a qədər massivi n uzunluğa qədər keçməyə başlayın. Cari array elementini ümumi maxPoint-ə daxil edin və hər dəfə döngədə i dəyəri artdıqda maxPoint-də saxlayın.

MaxValue dəyərini bir Tamsayı minimum dəyərinə qurun və etibarlı olduğu təqdirdə maxValue-nun maxPoint-dən böyük olmaması şansını yoxlayın, o zaman maxValue dəyərini maxPoint-dən yeniləyəcəyik, start s, 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 ilə yeniləməyimizə son verən var.

MaxPoint-in 0-dan az olub olmadığını yoxlayacağıq, bu sub-arrayın cəminin mənfi olmasını nəzərdə tutur, o zaman yenidən maxPoint dəyərini 0-a, s-ni i + 1-ə yeniləyəcəyik, bu 'olacaq' başlanğıc aralığının dəyərini təyin etməkdə bizə yenidən kömək edin və ən böyük cəm subarrayını tapmaqda bizə kömək edin. Bu maxPoint-i sıfır olaraq başlayacağıq, çünki ən böyük cəmi tapmalıyıq və sonra son başlanğıc + 1 kimi dəyəri qaytaracağıq. Bu qaytarma dəyəri, maksimum cəmin ən böyük alt sıra uzunluğu olacaqdır.

maksimum cəmi ilə subarray ölçüsüPin

Maksimum cəm ​​ilə subarray ölçüsünü tapmaq üçün C ++ dilində tətbiq

#include<bits/stdc++.h>

using namespace std;

int getSizeMaxSum (int arr[], int size)
{
    int maxVal = INT_MIN, maximumPoint = 0,
        start =0, end = 0, s=0;

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

        if (maxVal < maximumPoint)
        {
            maxVal = maximumPoint;
            start = s;
            end = i;
        }

        if (maximumPoint < 0)
        {
            maximumPoint = 0;
            s = i + 1;
        }
    }

    return (end - start + 1);
}
int main()
{
    int arr[] = {1, -2, 1, 1, -2, 1};
    int n = sizeof(arr)/sizeof(arr[0]);
    cout << getSizeMaxSum(arr, n);
    return 0;
}
2

 

Maksimum cəm ​​ilə subarray ölçüsü üçün Java-da tətbiqetmə

class SubArraySizeMaximumSum
{

    public static int getSizeMaxSum (int arr[], int size)
    {
        int maxVal = Integer.MIN_VALUE,
            maximumPoint = 0,start = 0,
            end = 0, s = 0;

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

            if (maxVal < maximumPoint)
            {
                maxVal = maximumPoint;
                start = s;
                end = i;
            }

            if (maximumPoint < 0)
            {
                maximumPoint = 0;
                s = i + 1;
            }
        }
        return (end - start + 1);
    }
    public static void main(String[] args)
    {
        int arr[] = {1, -2, 1, 1, -2, 1};
        int n = arr.length;
        System.out.println(getSizeMaxSum(arr, n));
    }
}
2

Mürəkkəblik təhlili

Zamanın mürəkkəbliyi

O (n) hara "N" massivdəki elementlərin sayıdır. Yalnız bir döngəni yalnız bir dəfə massivi keçmək üçün istifadə etdik, beləliklə onu xətti bir zaman mürəkkəbliyi həllinə çevirdik.

Kosmik Mürəkkəblik

O (n) hara "N" massivdəki elementlərin sayıdır. Tək bir n ölçülü bir sıra istifadə etdiyimiz üçün xətti kosmik mürəkkəbliyə də sahibik.

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