Үлкен қосалқы ішкі массив


Күрделілік дәрежесі оңай
Жиі кіреді 24 * 7 инновациялық зертханалар Акколит Amazon DE Шоу Factset Flipkart жорық Housing.com MakeMyTrip MetLife Microsoft Морган Стэнли Ola Cabs Oracle OYO бөлмелері PayU Samsung Шапшаң Терадата виза VMware Walmart зертханалары Зохо
Array Динамикалық бағдарламалау

Проблемалық мәлімдеме

Сізге бүтін сандар жиымы берілген. Проблемалық есепте ең үлкен қосындыны білуге ​​болады. Бұл берілген жиымдағы барлық басқа ішкі ішіліктердің ішіндегі ең үлкен қосындыға бағынатын (үздіксіз элементтер) табудан басқа ештеңе айтпайды.

мысал

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

Түсініктеме: 2 индексінен 4 индексіне дейінгі ішкі жиым массив ішіндегі ең үлкен 7-ге тең. Кез-келген басқа ішкі бөлім 7-ден кіші соманы береді.

Үлкен қосалқы ішкі массив

 

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

Түсініктеме: 2 индексінен 6 индексіне дейінгі ішкі жиым массив ішіндегі ең үлкен 10-ға ие.

 

Үлкен қосалқы субаррай проблемасының алгоритмі

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.

Түсіндіру

Біз ан массив бүтін сандар. Біз ең үлкен қосынды субарраны анықтауды сұрадық. Оның құрамында теріс және оң сандар болуы мүмкін. Біз сол жағдайлардың бәрін қарауымыз керек. Ол үшін біз массивті бір-ақ рет айналып өтеміз, демек оның күрделілік уақыты бар O (N). Сызықтық уақыттың күрделілігінде максималды сабақтас жиынтықты табамыз.

Сияқты кейбір мәндерді орнатыңыз maxValue Бүтін сан ең төменгі мәнге дейін, maxPoint 0-ге дейін, және бастау, соңы, және s дейін. Массивті ұзындыққа айналуды бастаңыз n. Жиынның ағымдағы элементін maxPoint қосындысына қосыңыз. Әр уақыт сайын оны maxPoint-та сақтаңыз i циклдегі өсім, біз бұл әрекетті орындаймыз. Біз қазірдің өзінде мәнін орнаттық maxValue Бүтін санның минималды мәніне дейін және maxValue maxPoint-тен аз екенін тексеріңіз. Егер бұл шын болса, біз maxValue мәнін maxPoint-тен жаңартамыз, s-ге бастаңыз. Бұл старт айнымалысы іргелес ішкі жиымның басталу диапазонының мәнін орнатады және бізде соңы бар (цикл айнымалысы).

Қазір тексереміз maxPoint 0-ден аз болса, массив мәндерінің осы уақытқа дейін қосылуын теріс деп санайды. Содан кейін біз maxPoint мәнін 0-ге, ал s + i + 1-ге жаңартамыз. Бұл s бастапқы диапазонның мәнін орнатуда бізге тағы да көмектеседі және ең үлкен қосалқы жиынды анықтауға көмектеседі. Бұл maxPoint нольге инициализацияланады, өйткені біз ең үлкен қосындыны табуымыз керек, содан кейін біз басталу мен аяқталу мәндерін қажетті ең үлкен қосалқы жиымның басталатын және аяқталатын белгісі ретінде шығарамыз. Егер осы тәсілді қолдансақ, біз бір жолда ең үлкен қосынды субарраны таба аламыз.

 

Қосымша субарреяның ең үлкен қосындысының коды

C ++ коды

#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 коды

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

Күрделілікті талдау

Уақыттың күрделілігі

Біз n өлшемді енгізу массивінің үстінде бір цикл жүргізіп жатқандықтан. Сонымен, ең үлкен қосынды қосалқы массивтің алгоритмі уақыттың сызықтық күрделілігіне ие. O (N) қайда «N» - бұл массивтегі элементтер саны.

Ғарыштың күрделілігі

Біз бүтін сандарды сақтау үшін 1D енгізу жиымын қолдандық. Осылайша, ең үлкен қосынды субаррай проблемасына сызықтық кеңістіктің күрделілігін қосады. O (N) қайда «N» - бұл массивтегі элементтер саны.