அருகிலுள்ளவர்களுக்கிடையேயான வேறுபாடு ஒன்றுதான்


சிரமம் நிலை எளிதாக
அடிக்கடி கேட்கப்படுகிறது அமேசான் Avalara உண்மை ஃபோர்கைட்டுகள் மைக்ரோசாப்ட்
அணி டைனமிக் புரோகிராமிங் LIS

“அருகிலுள்ளவர்களுக்கிடையேயான வேறுபாடு ஒன்றுதான்” என்ற சிக்கல் உங்களுக்கு வழங்கப்படுகிறது என்று கூறுகிறது முழு வரிசை. அருகிலுள்ள உறுப்புகளின் வேறுபாடு 1 ஆக இருக்கும் நீண்ட நீளத்தின் நீளத்தை இப்போது நீங்கள் கண்டுபிடிக்க வேண்டும்.

உதாரணமாக

அருகிலுள்ளவர்களுக்கிடையேயான வேறுபாடு ஒன்றுதான்

1 2 3 4 7 5 9 4
6

விளக்கம்

நிபந்தனையைப் பின்பற்றும் இரண்டு தொடர்ச்சிகள் இருப்பதை நாம் காணலாம். அவை {1, 2, 3, 4, 5, 4}, மற்றொன்று {7, 8 is. எனவே மிக நீண்ட தொடர்ச்சியானது முதல் ஒன்றாகும். இவ்வாறு பதில் 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

சிக்கலான பகுப்பாய்வு

நேர சிக்கலானது

ஓ (என் ^ 2), எங்களிடம் இரண்டு சுழல்கள் இருந்தன. ஒன்று வெறுமனே அனைத்து உறுப்புகளையும் கடந்து சென்றது, மற்றொன்று பயணித்த அனைத்து உறுப்புகளையும் கடந்து செல்கிறது. இதனால் வழிமுறைக்கான நேர சிக்கலானது பல்லுறுப்புறுப்பாக மாறுகிறது.

விண்வெளி சிக்கலானது

ஓ (என்), நாங்கள் இப்போது வரை பயணித்த அனைத்து கூறுகளுக்கும் முடிவை சேமிக்க வேண்டியிருந்தது. இதனால் விண்வெளி சிக்கலானது நேரியல் ஆகும்.