അടുത്തുള്ളവർ തമ്മിലുള്ള വ്യത്യാസം ഒന്നാണ്


വൈഷമ്യ നില എളുപ്പമായ
പതിവായി ചോദിക്കുന്നു ആമസോൺ അവലാര ഫാക്റ്റ്സെറ്റ് ഫോർകൈറ്റുകൾ മൈക്രോസോഫ്റ്റ്
അറേ ഡൈനാമിക് പ്രോഗ്രാമിംഗ് ലിസ്

“സമീപത്തുള്ളവർ തമ്മിലുള്ള വ്യത്യാസം ഒന്നാണ്” എന്ന പ്രശ്നം നിങ്ങൾക്ക് ഒരു നൽകിയിട്ടുണ്ടെന്ന് പറയുന്നു പൂർണ്ണസംഖ്യ ശ്രേണി. അടുത്തുള്ള മൂലകങ്ങളുടെ വ്യത്യാസം 1 ആയതിനേക്കാൾ ദൈർഘ്യമേറിയ തുടർന്നുള്ള ദൈർഘ്യം ഇപ്പോൾ നിങ്ങൾ കണ്ടെത്തേണ്ടതുണ്ട്.

ഉദാഹരണം

അടുത്തുള്ളവർ തമ്മിലുള്ള വ്യത്യാസം ഒന്നാണ്

1 2 3 4 7 5 9 4
6

വിശദീകരണം

ഈ അവസ്ഥയെ പിന്തുടരുന്ന രണ്ട് തുടർച്ചകളുണ്ടെന്ന് നമുക്ക് കാണാൻ കഴിയും. അവ {1, 2, 3, 4, 5, 4}, മറ്റൊന്ന് {7, 8 are. അതിനാൽ ഏറ്റവും ദൈർഘ്യമേറിയ ആദ്യത്തേത് ആദ്യത്തേതാണ്. ഇപ്രകാരം ഉത്തരം 6 ആണ്.

അടുത്തുള്ളവർ തമ്മിലുള്ള വ്യത്യാസം ഒന്നായതിനാൽ ഏറ്റവും ദൈർഘ്യമേറിയ തുടർന്നുള്ള സമീപനം

നിഷ്കളങ്കമായ ഒരു സമീപനം അത്തരം സാധ്യമായ തുടർന്നുള്ള തലമുറകളായിരിക്കും. എന്നാൽ തുടർന്നുള്ള തലമുറകൾ വളരെ സമയമെടുക്കുന്ന ജോലിയാണെന്ന് നമുക്കറിയാം. ഇതിന് ആവർത്തനം ആവശ്യമായി വരുന്നതിനാൽ എക്‌സ്‌പോണൻഷ്യൽ സമയ സങ്കീർണ്ണതയുണ്ട്. അതിനാൽ പ്രശ്നം പരിഹരിക്കുന്നതിന്, ഞങ്ങൾക്ക് ഒരു മികച്ച സമീപനം ആവശ്യമാണ്. ഒരു മികച്ച സമീപനം ആയിരിക്കും ഡൈനാമിക് പ്രോഗ്രാമിംഗ്. കാരണം പ്രശ്നം ദൈർഘ്യമേറിയ വർദ്ധിച്ചുവരുന്ന പ്രശ്നത്തിന് സമാനമാണ്. ഈ പ്രശ്‌നത്തിൽ‌, അടുത്തുള്ള ഘടകങ്ങൾ‌ക്ക് 1 വ്യത്യാസമുണ്ടായിരിക്കേണ്ട ഏറ്റവും ദൈർ‌ഘ്യമേറിയ തുടർ‌നടപടികൾ‌ ഞങ്ങൾ‌ കണ്ടെത്തേണ്ടതുണ്ട്. അതിനാൽ‌, പ്രശ്‌നം പരിഹരിക്കുന്നതിന് ഇൻ‌പുട്ട് അറേയിലെ ഘടകങ്ങളെ മറികടക്കാൻ ഞങ്ങൾ‌ ആരംഭിക്കുന്നു.

സഞ്ചരിക്കുന്നതിന് മുമ്പ് ഞങ്ങളുടെ ആദ്യത്തെ ഘടകമായ അടിസ്ഥാന കേസ് ഞങ്ങൾ സജ്ജമാക്കി. നമുക്ക് എല്ലായ്പ്പോഴും ദൈർഘ്യം 1 ന്റെ തുടർച്ച സൃഷ്ടിക്കാൻ കഴിയും. നമ്മൾ ഒരൊറ്റ ഘടകം തിരഞ്ഞെടുക്കുകയാണെങ്കിൽ. ഇപ്പോൾ നമ്മൾ മുന്നോട്ട് പോകുമ്പോൾ, ഒരു പിന്നോക്ക ദിശയിൽ പരിശോധിച്ചുകൊണ്ടിരിക്കും, നിലവിലെ മൂലകവുമായി 1 എന്ന കേവല വ്യത്യാസമുള്ള ഒരു മൂലകം എങ്ങനെയെങ്കിലും കണ്ടെത്തിയാൽ. അതിനുശേഷം നമുക്ക് നിലവിലെ മൂലകത്തെ അതിന്റെ അവസാന ഘടകമായി മറ്റ് ഘടകങ്ങളുള്ള തുടർന്നുള്ള ഘട്ടത്തിലേക്ക് ചേർക്കാൻ കഴിയും. അത്തരമൊരു ഘടകം കണ്ടെത്തുമ്പോൾ, നിലവിലെ ഘടകത്തിൽ അവസാനിക്കുന്ന തുടർന്നുള്ള പരമാവധി ദൈർഘ്യം ഞങ്ങൾ അപ്‌ഡേറ്റുചെയ്യുന്നു. ഈ മൂല്യങ്ങളെല്ലാം കണക്കുകൂട്ടിയ ശേഷം, ഈ മൂല്യങ്ങളുടെ പരമാവധി എണ്ണം ഞങ്ങൾ കണ്ടെത്തുന്നു. അതാണ് ഞങ്ങളുടെ പ്രശ്‌നത്തിനുള്ള ഉത്തരം.

കോഡ്

ഏറ്റവും ദൈർഘ്യമേറിയ തുടർന്നുള്ള സി ++ കോഡ്, സമീപത്തുള്ളവർ തമ്മിലുള്ള വ്യത്യാസം ഒന്നാണ്

#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), കാരണം ഞങ്ങൾക്ക് രണ്ട് ലൂപ്പുകൾ ഉണ്ടായിരുന്നു. ഒന്ന് കേവലം എല്ലാ മൂലകങ്ങളിലേക്കും സഞ്ചരിക്കുന്നു, മറ്റൊന്ന് സഞ്ചരിച്ച എല്ലാ മൂലകങ്ങളിലേക്കും സഞ്ചരിക്കുന്നു. അങ്ങനെ അൽഗോരിത്തിന്റെ സമയ സങ്കീർണ്ണത പോളിനോമിയലായി മാറുന്നു.

ബഹിരാകാശ സങ്കീർണ്ണത

O (N), ഞങ്ങൾ ഇതുവരെ സഞ്ചരിച്ച എല്ലാ ഘടകങ്ങൾക്കും ഫലം സംഭരിക്കേണ്ടതിനാൽ. അങ്ങനെ സ്ഥല സങ്കീർണ്ണത രേഖീയമാണ്.