أطول تتابع بحيث يكون الفرق بين المتجاورات واحدًا


مستوى الصعوبة سهل
كثيرا ما يطلب في أمازون Avalara مجموعة الحقائق فوركايتس Microsoft
مجموعة البرمجة الديناميكية LIS

توضح مشكلة "أطول فترة لاحقة بحيث يكون الاختلاف بين المتجاورات واحدًا" أنك تحصل على قيمة عدد صحيح مجموعة. أنت الآن بحاجة إلى إيجاد طول أطول سلسلة متتالية بحيث يكون فرق العناصر المتجاورة 1.

مثال

أطول تتابع بحيث يكون الفرق بين المتجاورات واحدًا

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

تحليل التعقيد

تعقيد الوقت

يا (N ^ 2) ، لأن لدينا حلقتين. أحدهما كان ببساطة يجتاز كل العناصر والآخر يمر فوق كل العناصر التي تم اجتيازها. وهكذا يصبح التعقيد الزمني للخوارزمية متعدد الحدود.

تعقيد الفضاء

O (N) حيث كان علينا تخزين النتيجة لجميع العناصر التي اجتزناها حتى الآن. وبالتالي فإن تعقيد الفضاء خطي.