सबसे लंबे समय तक अनुवर्ती कि आसन्न के बीच अंतर एक है


कठिनाई स्तर आसान
में अक्सर पूछा वीरांगना Avalara FactSet चौपाई माइक्रोसॉफ्ट
ऐरे गतिशील प्रोग्रामिंग एलआईएस

समस्या "सबसे लंबे समय तक चलने वाली स्थिति जैसे कि आसन्न के बीच का अंतर एक है" बताता है कि आपको ए पूर्णांक सरणी। अब आपको सबसे लंबे परिणाम की लंबाई खोजने की आवश्यकता है जैसे कि आसन्न तत्वों का अंतर 1 है।

उदाहरण

सबसे लंबे समय तक अनुवर्ती कि आसन्न के बीच अंतर एक है

1 2 3 4 7 5 9 4
6

व्याख्या

जैसा कि हम देख सकते हैं कि हालत का पालन करने वाले दो परिणाम हैं। वे {1, 2, 3, 4, 5, 4} हैं और दूसरे में {7, 8} हैं। तो सबसे लंबे समय तक बाद वाला पहला है। इस प्रकार उत्तर ६ है।

सबसे लंबे समय तक परिणाम के लिए दृष्टिकोण कि आसन्न के बीच अंतर एक है

एक भोली दृष्टिकोण ऐसे संभावित बाद की पीढ़ी होगी। लेकिन हम जानते हैं कि बाद की पीढ़ी बहुत समय लेने वाला काम है। चूंकि इसमें पुनरावृत्ति की आवश्यकता होगी और यह घातीय समय की जटिलता है। इसलिए समस्या को हल करने के लिए, हमें एक बेहतर दृष्टिकोण की आवश्यकता है। बेहतर दृष्टिकोण होगा गतिशील प्रोग्रामिंग। क्योंकि समस्या सबसे लंबे समय तक बढ़ने वाली उप-प्रक्रिया के समान है। इस समस्या में, हमें सबसे लंबे समय तक परिणाम को खोजने की आवश्यकता है, जिसके आसन्न तत्वों में 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

जटिलता विश्लेषण

समय जटिलता

ओ (एन ^ 2), क्योंकि हमारे पास दो छोर थे। एक बस सभी तत्वों पर ट्रेसिंग कर रहा था और दूसरा उन सभी तत्वों पर ट्रेस कर रहा है जो ट्रैवर्स किए गए हैं। इस प्रकार एल्गोरिथ्म के लिए समय की जटिलता बहुपद बन जाती है।

अंतरिक्ष जटिलता

पर), चूँकि हमें उन सभी तत्वों के लिए परिणाम को संग्रहीत करना था जिन्हें हमने अब तक ट्रेस किया था। इस प्रकार अंतरिक्ष जटिलता रैखिक है।