ყველაზე დიდი თანმიმდევრული ქვეჯგუფი


Რთული ტური Easy
ხშირად ეკითხებიან 24 * 7 ინოვაციის ლაბორატორია თანამოსაყრელი Amazon დე შოუ ფაქტები Flipkart ლაშქრობა საცხოვრებელი. Com MakeMyTrip MetLife microsoft Morgan Stanley ოლა კაბინები Oracle OYO ოთახები პეუ Samsung Snapdeal Teradata Visa VMware Walmart Labs Zoho
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 0. დაიწყეთ მასივის გადაკვეთა სიგრძეზე n. დაამატეთ მასივის ამჟამინდელი ელემენტი ჯამში maxPoint. შეინახეთ იგი maxPoint– ში, ყოველ ჯერზე i მარყუჟში იზრდება, ჩვენ ვაკეთებთ ამ ოპერაციას. ჩვენ უკვე დავაფიქსირეთ maxValue Integer- ის მინიმალური მნიშვნელობამდე და შეამოწმეთ maxValue ნაკლებია maxPoint- ზე. თუ ეს სიმართლეა, ჩვენ ვაპირებთ maxValue მნიშვნელობის განახლებას maxPoint– დან, დავიწყოთ s. ეს საწყისი ცვლადი შექმნის მომიჯნავე ქვე-მასივის საწყისი დიაპაზონის მნიშვნელობას და გვაქვს დასრულება, რომელსაც ვაახლებთ i (მარყუჟის ცვლადით).

ახლა გადავამოწმებთ თუ არა 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

 

ჯავის კოდი

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) სადაც "ნ" არის მასივის ელემენტების რაოდენობა.

სივრცის სირთულე

ჩვენ გამოვიყენეთ ერთი 1D შეყვანის მასივი მთელი რიცხვების შესანახად. ამრიგად, წრფივი სივრცის სირთულე შეიტანება უდიდესი თანმიმდევრული ქვეჯგუფის პრობლემას. O (n) სადაც "ნ" არის მასივის ელემენტების რაოდენობა.