გრძელი თანმიმდევრობა ისეთი, რომ სხვაობა მეზობლებს შორის ერთია  


Რთული ტური Easy
ხშირად ეკითხებიან Amazon ავალარა ფაქტები ფურკიტები microsoft
Array დინამიური პროგრამირება DSL

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

მაგალითი  

გრძელი თანმიმდევრობა ისეთი, რომ სხვაობა მეზობლებს შორის ერთიაPin

1 2 3 4 7 5 9 4
6

განმარტება

როგორც ვხედავთ, ორი პირობითობაა, რომლებიც პირობას მისდევს. ისინი არიან {1, 2, 3, 4, 5, 4} და მეორე არის {7, 8}. ასე რომ, ყველაზე გრძელი თანმიმდევრობა პირველია. ამრიგად, პასუხია 6.

გრძელი თანმიმდევრობის მიდგომა ისეთია, რომ სხვაობა მეზობლებს შორის ერთია  

გულუბრყვილო მიდგომა იქნება ასეთი შესაძლო ქვეცნობიერების წარმოქმნა. მაგრამ ჩვენ ვიცით, რომ ქვედანაყოფების წარმოება ძალიან შრომატევადი ამოცანაა. ვინაიდან ეს მოითხოვს რეკურსიას და არის ექსპონენციალური დროის სირთულე. ასე რომ, პრობლემის მოსაგვარებლად, ჩვენ უკეთეს მიდგომას ვითხოვთ. უკეთესი მიდგომა იქნება დინამიური პროგრამირება. რადგან პრობლემა მსგავსია ყველაზე გრძელი მომდევნო შედეგისა. ამ პრობლემის დროს, ჩვენ უნდა ვიპოვოთ ყველაზე გრძელი თანმიმდევრობა, რომლის მიმდებარე ელემენტებს უნდა ჰქონდეთ 1 სხვაობა. ამრიგად, პრობლემის გადასაჭრელად დავიწყებთ შეყვანის მასივის ელემენტების გადახედვას.

გადაკვეთის დაწყებამდე ჩვენ დავაყენეთ ჩვენი ძირითადი საქმე, რომელიც ჩვენი პირველი ელემენტია. ყოველთვის შეგვიძლია შევქმნათ სიგრძის 1. მიმდევრობა. თუ ვირჩევთ ერთ ელემენტს. ახლა, როდესაც ჩვენ წინ მივდივართ, ჩვენ გავაგრძელებთ უკანა მიმართულებით შემოწმებას, თუ როგორმე ვიპოვით ელემენტს, რომელსაც აქვს აბსოლუტური განსხვავება 1 – ით მიმდინარე ელემენტთან. მაშინ ჩვენ შეგვიძლია უბრალოდ დავამატოთ მიმდინარე ელემენტი თანმიმდევრობას, რომელსაც სხვა ელემენტი ჰქონდა, როგორც ბოლო ელემენტი. და როდესაც ჩვენ ვხვდებით ასეთ ელემენტს, ჩვენ განვაგრძობთ მაქსიმალური სიგრძის განახლებას ჩვენი თანმიმდევრობისთვის, რომელიც მიმდინარე ელემენტზე მთავრდება. და ამ ყველა მნიშვნელობის გამოთვლის შემდეგ, ჩვენ ყველა ამ მნიშვნელობის მაქსიმუმს ვხვდებით. ეს არის ჩვენი პრობლემის პასუხი.

იხილეთ ასევე
მასივის დალაგება სტეკების გამოყენებით

კოდი  

გრძელი თანმიმდევრობის C ++ კოდი ისეთი, რომ სხვაობა მეზობლებს შორის ერთია

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int input[] = {1, 2, 3, 4, 5, 7, 8, 4};
    int n = (sizeof input)/(sizeof input[0]);
    int dp[n];memset(dp, 0, sizeof dp);
    dp[0] = 1;
    for(int i=1;i<n;i++){
        for(int j=i;j>=0;j--)
            if(abs(input[i]-input[j]) == 1)
                dp[i] = max(dp[i], dp[j]+1);
    }
    int answer = 0;
    for(int i=0;i<n;i++)
        answer = max(answer, dp[i]);
    cout<<answer;
}
6

გრძელი მიმდევრობის ჯავის კოდი ისეთი, რომ სხვაობა მეზობლებს შორის ერთია

import java.util.*;

class Main{
  public static void main(String[] args){
      int input[] = {1, 2, 3, 4, 5, 7, 8, 4};
      int n = input.length;
      int dp[] = new int[n];
      for(int i=1;i<n;i++)dp[i] = 0;

      dp[0] = 1;
      for(int i=1;i<n;i++){
          for(int j=i;j>=0;j--)
              if(Math.abs(input[i]-input[j]) == 1)
                  dp[i] = Math.max(dp[i], dp[j]+1);
      }
      int answer = 0;
      for(int i=0;i<n;i++)
          answer = Math.max(answer, dp[i]);
      System.out.print(answer);
  }
}
6

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

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

O (N ^ 2), რადგან ორი მარყუჟი გვქონდა. ერთი უბრალოდ გადაჰყავდა ყველა ელემენტს და მეორე გადალახავდა ყველა ელემენტს. ამრიგად, დროის სირთულე ალგორითმისთვის მრავალხმიანად იქცევა.

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

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