ప్రక్కనే ఉన్నవారి మధ్య వ్యత్యాసం ఒకటి


కఠినత స్థాయి సులువు
తరచుగా అడుగుతుంది అమెజాన్ అవలారా ఫాక్ట్‌సెట్ ఫోర్కైట్స్ మైక్రోసాఫ్ట్
అర్రే డైనమిక్ ప్రోగ్రామింగ్ ఎల్.ఐ.ఎస్

“ప్రక్కనే ఉన్నవారి మధ్య వ్యత్యాసం ఒకటి” అనే సమస్య మీకు ఇవ్వబడింది పూర్ణ సంఖ్య అమరిక. ఇప్పుడు మీరు ప్రక్కనే ఉన్న మూలకాల వ్యత్యాసం 1 గా ఉండే పొడవైన తరువాతి పొడవును కనుగొనాలి.

ఉదాహరణ

ప్రక్కనే ఉన్నవారి మధ్య వ్యత్యాసం ఒకటి

1 2 3 4 7 5 9 4
6

వివరణ

పరిస్థితిని అనుసరించే రెండు పరిణామాలు ఉన్నాయని మనం చూడవచ్చు. అవి {1, 2, 3, 4, 5, 4} మరియు మరొకటి {7, 8 is. కాబట్టి పొడవైన తదుపరిది మొదటిది. అందువలన సమాధానం 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

సంక్లిష్టత విశ్లేషణ

సమయం సంక్లిష్టత

O (N ^ 2), ఎందుకంటే మాకు రెండు ఉచ్చులు ఉన్నాయి. ఒకటి కేవలం అన్ని మూలకాలపై ప్రయాణిస్తున్నది మరియు మరొకటి ప్రయాణించిన అన్ని అంశాలపై ప్రయాణిస్తుంది. అందువల్ల అల్గోరిథం యొక్క సమయ సంక్లిష్టత బహుపది అవుతుంది.

అంతరిక్ష సంక్లిష్టత

పై), మేము ఇప్పటివరకు ప్రయాణించిన అన్ని మూలకాల కోసం ఫలితాన్ని నిల్వ చేయాల్సి వచ్చింది. అందువలన స్థల సంక్లిష్టత సరళంగా ఉంటుంది.