الحد الأقصى للطول اللاحق مع الاختلاف بين العناصر المتجاورة إما 0 أو 1


مستوى الصعوبة متوسط
كثيرا ما يطلب في سيسكو اكسبيديا Qualtrics مختبرات SAP مقاومه
مجموعة البرمجة الديناميكية

المشكلة بيان

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

مثال

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

تفسير

النتيجة = 4، 5، 6، 5، 4

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

تفسير

النتيجة = -3 ، -2 ، -1 ، -2 ، -3 ، -4

خوارزمية للعثور على الحد الأقصى للطول التالي مع اختلاف بين العناصر المتجاورة إما 0 أو 1

1. Declare a Map.
2. Set maxValue to 0.
3. Traverse the array starting from i=0 to while i<n (length of the array).
  1. Initialize a variable temp to 0.
  2. Check if Map contains the key as arr[i-1],
    1. If true, then get the value of arr[i-1] and store it to temp.
  3. Check if Map contains the key as arr[i],
    1. If true, then find the greater between the temp and the value of arr[i] in the map, and store it to temp.
  4. Check if Map contains the key as arr[i+1],
    1. If true, then find the greater between the temp and the value of arr[i+1] in the map, and store it to temp.
  5. Check if the temp is greater than maxValue,
    1. If true then store the value of temp to maxValue.
  6. And put the arr[i] as a key and temp as a value into the map.
4. Return maxValue.

تفسير

لقد حصلنا على عدد صحيح المصفوفة ، تطلب بيانات المشكلة معرفة الحد الأقصى لطول التتابع اللاحقة. ويجب أن تكون النتيجة اللاحقة المختارة بحيث لا يوجد فرق بين القيم المتجاورة بخلاف 0 أو 1. لحل هذا سنستخدم الثرم لجعل حلنا فعالاً. سنضع المفتاح كعنصر في المصفوفة ونأخذ قيمة المفتاح دائمًا للعثور على القيمة القصوى وتخزينها في درجة الحرارة.

دعونا نفكر في مثال ونفهم هذا:

مثال

وصول [] = {1 ، 4 ، 5 ، 2 ، 6 ، 5 ، 4 ، 8}

أول شيء نفعله هو التصريح عن ملف رسم خريطة لأننا سنقوم بتخزين عنصر مصفوفة وقيمة درجة الحرارة وفقًا للخوارزمية التي ناقشناها. عيّن قيمة maxValue إلى 0. سنقوم بإرجاع هذا المتغير. ما هو في هذا المتغير سيكون إجابتنا. سنجتاز المصفوفة ونجعلها تصل إلى طول المصفوفة. في كل مرة نجتاز فيها المصفوفة بالقيمة الجديدة i ، نقوم بتهيئة قيمة temp إلى 0.

i = 0، arr [i] = 1، temp = 0، maxValue = 0 Map = {}

تحقق من الشرط الذي سيتم الوفاء به. في هذه الحالة لا يوجد شرط. لذلك فهو يعمل temp ++ ويتحقق مما إذا كانت درجة الحرارة أكبر من maxValue. إذا كان هذا صحيحًا ، فقم بتخزين درجة الحرارة في maxValue وأدخل القيمة والدرجة الحرارة في الخريطة.

i = 1، arr [i] = 4، temp = 0، maxValue = 1.

الخريطة = {1,1،XNUMX}

كما هو مذكور أعلاه ، نقوم فقط بإدراج القيم في الخريطة

i = 2، arr [i] = 5، temp = 0، maxValue = 1.

الخريطة = {1: 1 ، 4: 1}

هذه المرة نجد الشرط الأول الصحيح الذي تحتوي الخريطة على arr [i] -1 وهو 4. لذلك يأخذ الرقم 1 كدرجة حرارة ونفعل temp ++. ثم قم بتغيير maxValue إلى 2 وأدخل arr [i] ودرجة الحرارة فيه.

وبهذه الطريقة ، سنواصل التحقق من الشروط ونأخذ القيم في درجة الحرارة. استمر في إدراجه في الخريطة ، أخيرًا ، نحصل على القيمة في maxValue كإخراج لدينا.

الحد الأقصى للطول اللاحق مع الاختلاف بين العناصر المتجاورة إما 0 أو 1

رمز

كود C ++ للعثور على الحد الأقصى للطول التالي مع وجود اختلاف بين العناصر المجاورة إما 0 أو 1

#include<iostream>
#include<unordered_map>

using namespace std;

int getMaximumLenSubsequence(int arr[], int n)
{
    unordered_map<int, int> MAP;
    int maxValue = 0;
    for (int i=0; i<n; i++)
    {
        int temp = 0;
        if (MAP.find(arr[i]-1) != MAP.end() && temp < MAP[arr[i]-1])
            temp = MAP[arr[i]-1];

        if (MAP.find(arr[i]) != MAP.end() && temp < MAP[arr[i]])
            temp = MAP[arr[i]];

        if (MAP.find(arr[i]+1) != MAP.end() && temp < MAP[arr[i]+1])
            temp = MAP[arr[i]+1];

        MAP[arr[i]] = temp + 1;

        if (maxValue < MAP[arr[i]])
            maxValue = MAP[arr[i]];
    }
    return maxValue;
}
int main()
{
    int arr[] = {1, 4, 5, 2, 6, 5, 4, 8};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << getMaximumLenSubsequence(arr, n);
    return 0;
}
5

كود Java للعثور على الحد الأقصى للطول الذي يليه مع وجود اختلاف بين العناصر المتجاورة إما 0 أو 1

import java.util.HashMap;

class subsequenceLength
{
    public static int getMaximumLenSubsequence(int[] arr)
    {
        int maxValue = 0;
        HashMap<Integer, Integer> MAP = new HashMap<>();
        for (int i = 0; i < arr.length; i++)
        {
            int temp = 0;
            if (MAP.containsKey(arr[i] - 1))
            {
                temp = MAP.get(arr[i] - 1);
            }

            if (MAP.containsKey(arr[i]))
            {
                temp = Math.max(temp, MAP.get(arr[i]));
            }

            if (MAP.containsKey(arr[i] + 1))
            {
                temp = Math.max(temp, MAP.get(arr[i] + 1));
            }
            temp++;
            if (temp > maxValue)
            {
                maxValue = temp;
            }
            MAP.put(arr[i], temp);
        }
        return maxValue;
    }
    public static void main(String[] args)
    {
        int arr[] = { 1, 4, 5, 2, 6, 5, 4, 8};
        System.out.println(getMaximumLenSubsequence(arr));
    }
}
5

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

تعقيد الوقت

O (ن) أين "ن" هو عدد العناصر في المصفوفة. لقد اجتزنا ببساطة جميع العناصر في المصفوفة. نظرًا لأننا استخدمنا HashMap ، فقد تمكنا من القيام بذلك في تعقيد الوقت الخطي.

تعقيد الفضاء

O (ن) أين "ن" هو عدد العناصر في المصفوفة. نظرًا لأننا نقوم بتخزين البيانات المتعلقة بالعناصر الموجودة في الخريطة ، فإن تعقيد المساحة يكون أيضًا خطيًا.