Ири суммадагы туташ Subarray


Кыйынчылык деңгээли жеңил
Көп суралган 24 * 7 Innovation Labs Accolite Amazon DE Shaw Factset Flipkart селсаяктоо Housing.com MakeMyTrip MetLife Microsoft Морган Стэнли Ola Cabs Oracle OYO бөлмөлөр PayU Samsung Snapdeal Терадата виза VMware Walmart Labs Zoho
согуштук тизме Динамикалык программалоо

Маселени билдирүү

Сизге бүтүн сандардын массиви берилет. Көйгөйдүн баяндалышы эң чоң суммага жанаша subarray табууну суранат. Бул берилген массивдеги бардык башка ичкеликтердин ичинен эң чоң суммага ээ болгон субарраны (үзгүлтүксүз элементтерди) табуудан башка эч нерсе билдирбейт.

мисал

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

Түшүндүрүү: 2-индекстен 4-индекске чейинки суб-массив, массивдин ичинде эң чоң суммага ээ 7ге ээ. Башка подразделение 7ден кичине сумманы берет.

Ири суммадагы туташ Subarray

 

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

Түшүндүрмө: 2-индекстен 6-индекске чейинки суб-массив, массивдин ичиндеги эң чоң суммага ээ.

 

Ири суммага туташкан Subarray маселесинин алгоритми

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тен жаңыртабыз, с деп баштаңыз. Бул старттык өзгөрүлмө чектеш суб-массивдин баштапкы диапазонунун маанисин орнотот жана биз аягыбыз бар, аны i (цикл өзгөрмөсү) менен жаңыртабыз.

Азыр болсо текшеребиз maxPoint 0ден аз болсо, массивдин ушул убакка чейинки мааниси кошулганын билдирет. Андан кийин maxPoint маанисин 0 жана s + i 1 деп жаңыртабыз. Бул s баштапкы диапазондун маанисин коюуда бизге дагы бир жолу жардам берет жана эң чоң сумма подразделениесин табууга жардам берет. Бул maxPoint биз нөлгө башталат, анткени биз эң чоң сумманы билишибиз керек, андан кийин баштоо жана аяктоо маанисин эң чоң сумма суб-массивинин башталыш жана аяктоочу көрсөткүчү катары чыгарабыз. Эгерде ушул ыкманы колдонгон болсок, анда бир эле өтүштүн ичинде эң чоң суммадагы жанаша subarray табууга болот.

 

Ири суммадагы чектеш субаррай көйгөйүнүн коду

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 Code

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 киргизүү массивин колдондук. Ошентип, эң чоң сумма жанаша Subarray көйгөйүнө сызык мейкиндигинин татаалдыгын кошуу. O (N) кайда "N" массивдеги элементтердин саны.