Առավելագույն երկարության հետևանք ՝ հարակից տարրերի միջև տարբերությամբ կամ 0 կամ 1


Դժվարության մակարդակ Միջին
Հաճախակի հարցնում են Cisco Expedia Քվեարկողներ 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-ը: Դա լուծելու համար մենք կօգտագործենք ծիծաղել մեր լուծումը արդյունավետ դարձնելու համար: Մենք պատրաստվում ենք բանալին դնել որպես զանգվածի տարր և վերցնել ստեղնաշարի արժեքը միշտ գտնել առավելագույն արժեքը և պահել այն տեմպով:

Եկեք քննարկենք մի օրինակ և հասկանանք սա.

Օրինակ

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

Առաջին բանը, որ մենք անում ենք, հայտարարենք ա Քարտեզը քանի որ մենք պահելու ենք զանգվածի տարրը և արժեքի տեմպը ըստ մեր քննարկած ալգորիթմի: MaxValue- ի արժեքը դնել 0-ի: Մենք պատրաստվում ենք վերադարձնել այս փոփոխականը: Այն, ինչ կա այդ փոփոխականում, կլինի մեր պատասխանը: Մենք կշեղենք զանգվածը և կստիպենք այն հասնել զանգվածի երկարությանը: Ամեն անգամ, երբ զանգվածը հատում ենք i- ի նոր արժեքով, մենք սկզբնական արժեքը տալիս ենք 0-ի:

i = 0, arr [i] = 1, temp = 0, maxValue = 0 Քարտեզ = {}

Ստուգեք, թե որ պայմանը կկատարվի: Այս պարագայում ոչ մի պայման չկա: Այսպիսով, դա անում է temp ++ և ստուգում է, արդյոք temp- ն ավելի՞ մեծ է, քան maxValue- ից: Եթե ​​ճիշտ է, ապա պահեք temp- ը maxValue- ի մեջ և արժեքը և temp- ը տեղադրեք քարտեզի մեջ:

i = 1, arr [i] = 4, temp = 0, maxValue = 1:

Քարտեզ = {1,1}

Նույնը, ինչ վերը նշված պայմանը, մենք պարզապես տեղադրում ենք արժեքները քարտեզի մեջ

i = 2, arr [i] = 5, temp = 0, maxValue = 1:

Քարտեզ = {1: 1, 4: 1}

Այս անգամ մենք գտնում ենք, որ առաջին պայմանը ճիշտ է, որ քարտեզը պարունակում է arr [i] -1, այսինքն ՝ 4. Այսպիսով, այն 1-ը վերցնում է որպես temp և կատարում temp ++: Դրանից հետո փոխեք maxValue- ը 2-ի և տեղադրեք arr [i] և temp դրա մեջ:

Եվ պարզապես այսպես, մենք շարունակելու ենք ստուգել պայմանները և վերցնել արժեքները տեմպով: Շարունակեք այն մտցնել քարտեզի վրա, վերջապես, մենք ստանում ենք 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

Բարդության վերլուծություն

Timeամանակի բարդություն

O (n) որտեղ «Ն» զանգվածում տարրերի քանակն է: Մենք պարզապես թերթել ենք զանգվածի բոլոր տարրերը: Քանի որ մենք օգտագործել ենք HashMap- ը, մենք կարողացանք դա անել Գծային ժամանակի բարդության պայմաններում:

Տիեզերական բարդություն

O (n) որտեղ «Ն» զանգվածում տարրերի քանակն է: Քանի որ քարտեզում տարրերի հետ կապված տվյալներ ենք պահում, տարածության բարդությունը նույնպես գծային է: