ყველაზე გრძელი ბიტონიური შედეგი


Რთული ტური Hard
ხშირად ეკითხებიან CodeNation დე შოუ Google JP Morgan microsoft
Array დინამიური პროგრამირება

დავუშვათ, რომ თქვენ გაქვთ მასივი of მთელი რიცხვები, პრობლემის დებულება ითხოვს გრძელი ბიტონიური თანმიმდევრობის გარკვევას. მასივის ბიტონიური თანმიმდევრობა ითვლება თანმიმდევრობით, რომელიც ჯერ იზრდება და შემდეგ იკლებს.

მაგალითი

arr[] = {1,4,2,76,43,78,54,32,1,56,23}
7

განმარტება

1 4 76 78 54 32 23 (პირველი იზრდება 78-მდე და შემდეგ მცირდება 23-მდე.

ყველაზე გრძელი ბიტონიური შედეგი

 

ალგორითმი

  1. მასივის გამოცხადება მზარდი Seq [] ზომა იგივეა, რაც მოცემული მასივის სიგრძე.
  2. ყველა ინდექსის ელემენტის ინიციალიზაცია, როგორც შექმნილი მასივის 1 მზარდი Seq [].
  3. შეიტყვეთ ყველაზე გრძელი მზარდი თანმიმდევრობა მისი მზარდი Seq- ში [] მარცხნიდან მარჯვნივ შენახვით.
  4. მასივის გამოცხადება შემცირება Seq [] ზომა იგივეა, რაც მოცემული მასივის სიგრძე.
  5. იპოვნეთ გრძელი კლებადი მიმდევრობის გადაადგილება მარჯვნივ მარცხნიდან და მისი შემცირება Seq- ში [].
  6. ცვლადის ინიციალიზაცია, რომელიც მაქსოუთუთს ატარებს, იზრდებაSeq [0] + შემცირება Seq [0] - ზე.
  7. შეიტყვეთ მაქსიმუმი იზრდება Seq [i] + მცირდება Seq [i] - 1 და შეინახეთ maxOutput- ში.
  8. დააბრუნე maxOutput.

განმარტება

N ზომის შეყვანის მასივი შედგება დადებითი მთელი რიცხვებისგან. ჩვენ გვთხოვენ გავერკვიოთ მოცემული მასივის გრძელი ბიტონიური თანმიმდევრობა. ბიტონიური თანმიმდევრობა შეიძლება განისაზღვროს, როგორც თანმიმდევრობა, რომელიც პირველი იზრდება, რაც ნიშნავს, რომ რიგით რიცხვში პირველი იზრდება. შემდეგ რიცხვი მცირდება მიმდევრობის დასრულებამდე. ჩვენ უნდა განვსაზღვროთ გრძელი ბიტონიური თანმიმდევრობის სიგრძე.

პირველი, გამოყოფა გამოყოფა ორ ნაწილად. ჩვენ ვაცხადებთ ორ მასივს, პირველი მასივი ითვლება მზარდი მასივი ყველაზე გრძელი მზარდი თანმიმდევრობა არის თანმიმდევრობა, რომელშიც რიცხვები უნდა იყოს პირველი მზარდი თანმიმდევრობით. ასე რომ, ჩვენ ვაპირებთ მასივის გადაკვეთას ჩასმულ მარყუჟში. განაგრძეთ მზარდი თანმიმდევრობის პოვნა. მაშინ უნდა შეამოწმოთ პირობა, რომ თუ ამჟამინდელი ელემენტი ნაკლებია შემდეგ ელემენტზე. ასევე მზარდი Seq- ის ამჟამინდელი ელემენტი ნაკლებია, ვიდრე მზარდი Seq- ის შემდეგი ელემენტი []. თუ სიმართლეა, შეინახეთ ელემენტი, როგორც зголемуваSeq [j] + 1. ეს ემატება მას შემდეგ, რაც მასივი უკვე დავიწყეთ მასში 1 – ის სახით.

მეორე, გამოაცხადეთ მასივი, მცირდება Seq []. ამ შემცირებული Seq [] - ში, ჩვენ ვაპირებთ მასივის გადალახვა ჩასმული მარყუჟის ფორმით, მასივიდან მარცხნივ მარცხნივ. ჩვენ ვაპირებთ შეამოწმოთ არის თუ არა ამჟამინდელი ელემენტი უფრო მეტი ვიდრე შემდეგი ელემენტი. იმიტომ, რომ ჩვენ გავდივართ მარჯვნივ მარცხნიდან. შემდეგ განაახლეთ იგი შემცირებადი Seq [i] - ით შემცირებადი Seq [j] +1 - ით. კოდის ბოლო ეტაპზე უნდა ვიპოვოთ მაქსიმალური Seq [i] + შემცირება Seq [i] - 1, რომელიც ინახება maxOutput- ში.

კოდი

C ++ კოდი გრძელი ბიტონიური თანმიმდევრობისთვის

#include<iostream>

using namespace std;

int BitonicSequence( int arr[], int n )
{
    int i, j;

    int *increasingSeq = new int[n];
    for (i = 0; i < n; i++)
        increasingSeq[i] = 1;

    for (i = 1; i < n; i++)
        for (j = 0; j < i; j++)
            if (arr[i] > arr[j] && increasingSeq[i] < increasingSeq[j] + 1)
                increasingSeq[i] = increasingSeq[j] + 1;

    int *decreasingSeq = new int [n];
    for (i = 0; i < n; i++)
        decreasingSeq[i] = 1;

    for (i = n-2; i >= 0; i--)
        for (j = n-1; j > i; j--)
            if (arr[i] > arr[j] && decreasingSeq[i] < decreasingSeq[j] + 1)
                decreasingSeq[i] = decreasingSeq[j] + 1;

    int maxOutput = increasingSeq[0] + decreasingSeq[0] - 1;

    for (i = 1; i < n; i++)
        if (increasingSeq[i] + decreasingSeq[i] - 1 > maxOutput)
            maxOutput = increasingSeq[i] + decreasingSeq[i] - 1;

    return maxOutput;

}
int main()
{
    int arr[] = {1,4,2,76,43,78,54,32,1,56,23};
    int n = sizeof(arr)/sizeof(arr[0]);
    cout<<"Length of Longest Bitonic Sequence is "<< BitonicSequence(arr, n);
    return 0;
}
Length of Longest Bitonic Sequence is 7

ყველაზე გრძელი ბიტონიური თანმიმდევრობის ჯავის კოდი

class longestBitonicSequence
{
    public static int BitonicSequence( int arr[], int n )
    {
        int i, j;

        int[] increasingSeq = new int[n];
        for (i = 0; i < n; i++)
            increasingSeq[i] = 1;

        for (i = 1; i < n; i++)
            for (j = 0; j < i; j++)
                if (arr[i] > arr[j] && increasingSeq[i] < increasingSeq[j] + 1)
                    increasingSeq[i] = increasingSeq[j] + 1;

        int[] decreasingSeq = new int [n];
        for (i = 0; i < n; i++)
            decreasingSeq[i] = 1;

        for (i = n-2; i >= 0; i--)
            for (j = n-1; j > i; j--)
                if (arr[i] > arr[j] && decreasingSeq[i] < decreasingSeq[j] + 1)
                    decreasingSeq[i] = decreasingSeq[j] + 1;


        int maxOutput = increasingSeq[0] + decreasingSeq[0] - 1;

        for (i = 1; i < n; i++)
            if (increasingSeq[i] + decreasingSeq[i] - 1 > maxOutput)
                maxOutput = increasingSeq[i] + decreasingSeq[i] - 1;

        return maxOutput;
    }

    public static void main (String[] args)
    {
        int arr[] = {1,4,2,76,43,78,54,32,1,56,23};
        int n = arr.length;
        System.out.println("Length of longest bitonic sequence is "+ BitonicSequence( arr, n ));
    }
}
Length of longest bitonic sequence is 7

სირთულის ანალიზი

დროის სირთულე

ო (ნ2სადაც "ნ" არის მასივის ელემენტების რაოდენობა. ვინაიდან ჩვენ ჩასმული მარყუჟი გამოვიყენეთ, რამაც ალგორითმი აწარმოა პოლინომის დროში.

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

O (n) სადაც "ნ" არის მასივის ელემენტების რაოდენობა. ვინაიდან ჩვენ გამოვიყენეთ ორი დამატებითი მასივი, რომელთა ზომა დამოკიდებულია შეყვანის მასივზე. სივრცის სირთულე ხაზოვანია.