Ամենաերկար հետևությունն այնպիսին է, որ հարևանների միջև տարբերությունը մեկն է


Դժվարության մակարդակ Հեշտ
Հաճախակի հարցնում են Amazon Ավալարա Փաստեր Ֆուրկիտներ Microsoft
Դասավորություն Դինամիկ ծրագրավորում ԱԱՀ

«Ամենաերկար հետևությունն այնպիսին է, որ հարևանների միջև տարբերությունը մեկն է» խնդիրը ասում է, որ ձեզ տրված է ամբողջ թիվ դասավորություն, Այժմ դուք պետք է գտնեք ամենաերկար հետևության երկարությունը այնպես, որ հարակից տարրերի տարբերությունը 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

Java- ի ամենաերկար հետևյալության ծածկագիրն այնպես, որ հարևանների միջև տարբերությունը մեկն է

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

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

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

O (N ^ 2), քանի որ մենք ունեինք երկու օղակ: Մեկն ուղղակի անցնում էր բոլոր տարրերի վրայով, իսկ մյուսը ՝ անցել բոլոր անցած տարրերի վրայով: Այսպիսով, ալգորիթմի համար ժամանակի բարդությունը դառնում է բազմանդամ:

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

ՎՐԱ), քանի որ մենք պետք է արդյունքը պահեինք մինչ այժմ մեր անցած բոլոր տարրերի համար: Այսպիսով, տարածության բարդությունը գծային է: