د ضمیمه عناصرو ترمینځ د 0 یا 1 په څیر د توپیر سره د اوږدوالي اعظمي حد


مشکل کچه منځني
په مکرر ډول دننه پوښتل کیږي سیسکو ايکسپيډيا کټتوریک د SAP لابراتوارونه Teradata
پیشه متحرک برنامې

ستونزه بیان

تاسو ته ورکول کیږي ضمیمه سور. ستونزه "د ضمیمه عناصرو تر مینځ توپیر سره د اوږدوالي اعظمي ضمني برخه لکه څنګه چې 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}

لومړی کار چې موږ یې کوو هغه د a اعلان کول نقشه ځکه چې موږ د الګوریتم له مخې چې موږ پرې بحث کړی یو سرنی عنصر او د ارزښت لنډمهاله زیرمو ته ځو. د maxValue ارزښت 0 ته وټاکئ. موږ دا تغیر بیرته راوړو. څه چې پدې متغیر کې دي زموږ ځواب به وي. موږ به د صف په اوږدو کې تیر کړو او دا به د صف په اوږدوالي ته ورسوو. هرځله چې موږ د i د نوي ارزښت سره ارې وباسو ، موږ 0 ته د ارزښت لنډمهاله پیل کوو.

i = 0 ، آر آر [i] = 1 ، لنډمهاله = 0 ، میکس ویلیو = 0 نقشه = {

وګورئ چې کوم حالت بشپړ کیږي. پدې حالت کې ، هیڅ شرط نشته. نو دا ټیم ++ کوي او چیک کوي که چیرې ټیمپ د میک ویولیو څخه لوی وي. که ریښتیا وي نو ټیمپ په میکس ویلیو کې ذخیره کړئ او ارزښت او لنډمهاله نقشه کې دننه کړئ.

i = 1 ، آر آر [i] = 4 ، لنډمهاله = 0 ، میکس ویلیو = 1.

نقشه = {1,1،XNUMX}

د پورتني حالت په څیر ورته ، موږ یوازې نقشه کې ارزښتونه دننه کوو

i = 2 ، آر آر [i] = 5 ، لنډمهاله = 0 ، میکس ویلیو = 1.

نقشه = {1: 1 ، 4: 1}

دا ځل موږ لومړی شرایط سم وموندل چې نقشه کې آرر [i] -1 دی چې 4 دی. نو دا د 1 وخت په توګه اخلي او ټیم ++ کوي. بیا میکس ویلیو 2 ته بدل کړئ او ارار داخل کړئ [i] او په کې یې دننه کړئ.

او په ساده ډول د دې په څیر ، موږ به شرایط معاینه کړو او ارزښتونه مو په لنډیز کې ونیسو. په نقشه کې یې دننه کولو ته دوام ورکړئ ، په نهایت کې ، موږ زموږ د محصول په توګه په میکس ویلیو کې ارزښت ترلاسه کوو.

د ضمیمه عناصرو ترمینځ د 0 یا 1 په څیر د توپیر سره د اوږدوالي اعظمي حد

کوډ

د ضمیمه عناصرو تر مینځ توپیر سره د 0 یا 1 په څیر د اوږدوالي اعظمي ضمني برخې موندلو لپاره C ++ کوډ

#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

د 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

د پیچلتیا تحلیل

د وخت پیچلتیا

اې (N) هلته "n" په صف کې د عناصرو شمیر دی. موږ په ساده ډول په صف کې د ټولو عناصرو څخه تېر شو. ځکه چې موږ د هش میپ کارولی دی موږ د دې وړ و چې دا د خط وخت پیچلتیا کې ترسره کړئ.

د ځای پیچلتیا

اې (N) هلته "n" په صف کې د عناصرو شمیر دی. له هغه وخته چې موږ په نقشه کې د عناصرو پورې اړوند معلومات ذخیره کوو ، نو د ځای پیچلتیا هم خطي ده.