जनरेट केलेले अ‍ॅरे लीटकोड सोल्यूशनमध्ये जास्तीत जास्त मिळवा


अडचण पातळी सोपे
अरे

तयार होणार्‍या अ‍ॅरे लिटकोड सोल्यूशनमध्ये मॅक्सिमम इन होण्यास समस्या आम्हाला एक पूर्णांक प्रदान करते. दिलेल्या सिंगल सह पूर्णांक, व्युत्पन्न केलेल्या अ‍ॅरेमध्ये आम्हाला जास्तीत जास्त पूर्णांक शोधणे आवश्यक आहे. अ‍ॅरे पिढीचे काही नियम आहेत. लागू केलेल्या मर्यादांनुसार, आम्हाला व्युत्पन्न केलेला जास्तीत जास्त पूर्णांक शोधणे आवश्यक आहे. नियम असेः

  1. अरे [0] = 0, अरे [1] = 1
  2. arr [2 * i] = अरे [i] जिथे 2 <= 2 * i <= n
  3. आणि अरर [२ * मी + १] = अरर [मी] + अर [आय + १] जिथे २ <= २ * मी + १ <= एन

पण यापुढे सोल्यूशनमध्ये डाईव्ह करण्यापूर्वी. आपण काही उदाहरणे पहायला पाहिजेत.

जनरेट केलेले अ‍ॅरे लीटकोड सोल्यूशनमध्ये जास्तीत जास्त मिळवा

n = 7
3

स्पष्टीकरण: दिलेल्या नियमांनुसारः
संख्या [0] = 0, क्रमांक [1] = 1
क्रमांक [(1 * 2) = 2] = क्रमांक [1] = 1
क्रमांक [(1 * 2) + 1 = 3] = क्रमांक [1] + संख्या [2] = 1 + 1 = 2
क्रमांक [(2 * 2) = 4] = क्रमांक [2] = 1
क्रमांक [(2 * 2) + 1 = 5] = क्रमांक [2] + संख्या [3] = 1 + 2 = 3
क्रमांक [(3 * 2) = 6] = क्रमांक [3] = 2
क्रमांक [(3 * 2) + 1 = 7] = क्रमांक [3] + संख्या [4] = 2 + 1 = 3

तर, आपण संख्या = [0,1,1,2,1,3,2,3] पाहू आणि त्यापैकी जास्तीत जास्त 3 आहे. असे उत्तर 3 आहे.

जनरेट केलेल्या अ‍ॅरे लीटकोड सोल्यूशनमध्ये मॅक्सिमम गेट मिळविण्याचा दृष्टिकोण

तयार होणार्‍या अ‍ॅरे लिटकोड सोल्यूशनमध्ये मॅक्सिमम इन होण्यास समस्या काही अडचणी आहेत ज्या समाधानी असणे आवश्यक आहे. दिलेल्या मर्यादांनुसार, आम्हाला जास्तीत जास्त पूर्णांक शोधणे आवश्यक आहे. अ‍ॅरे पिढीसाठी नियम आधीपासूनच समस्येच्या वर्णनात स्पष्ट केले गेले आहेत. मनातील पहिली पद्धत अ‍रेची पिढी आणि जास्तीत जास्त घटक शोधणे होय. पण त्या समस्येचे निराकरण होईल?

जर आम्ही पिढीबरोबर सहजपणे पुढे गेलो तर आम्हाला योग्य परिणाम सापडणार नाहीत. कारण आपण अ‍ॅरे कसे निर्माण करतो यावर अवलंबून आहे. आम्ही आयथ इंडेक्समध्ये असतो तेव्हा आम्ही 2 व्या आणि (2i + 1) निर्देशांकावर घटक व्युत्पन्न करतो. त्याक्षणी, आमच्याकडे (i + 1) व्या निर्देशांकासाठी व्युत्पन्न मूल्य नाही. अशा परिस्थितीत निकाल अचूक ठरणार नाही.

समस्येचे निराकरण करण्यासाठी, आम्ही घटक निर्मितीसाठीच्या सूत्रांमध्ये फेरफार करू. जर मी तिसर्‍या नियमात i-1 ने i ची जागा बदलली. आम्हाला ती एरर [3 * i-2] = अरर [i] + अर [i-1] आढळली. तर आता आपण अ‍ॅरे जनरेशन साठी नियम वापरू शकतो. कारण हा नियम आधीपासून व्युत्पन्न मूल्याचे मूल्य वापरतो. म्हणून भविष्यातील कोणतीही अज्ञात मूल्ये वापरण्याऐवजी आम्ही पूर्व-गणना केलेली मूल्ये वापरत आहोत. आता आम्ही फक्त for लूप वापरुन संपूर्ण प्रक्रिया सिम्युलेट करतो आणि 1 * i आणि 2 * i-2 अ‍ॅरेच्या हद्दीत असल्याचे तपासते. एकदा याची खात्री झाल्यावर अ‍ॅरे भरण्यासाठी आम्ही फॉर्म्युले वापरतो.

कोड

जनरेट केलेल्या अ‍ॅरे लीटकोड सोल्यूशनमध्ये गेट मॅक्सिममसाठी सी ++ कोड

#include <bits/stdc++.h>
using namespace std;

int getMaximumGenerated(int n) {
    if(n == 0)return 0;
    if(n == 1)return 1;
    vector<int> tmp(n+1);
    tmp[0] = 0;
    tmp[1] = 1;
    for(int i=1;i<=n;i++){
        if(2*i<=n)
            tmp[2*i] = tmp[i];
        if(2*i-1<=n)
            tmp[2*i-1] = tmp[i] + tmp[i-1];
    }
    int ans = 0;
    for(int i=0;i<=n;i++)
        ans = max(tmp[i], ans);
    return ans;
}

int main(){
    cout<<getMaximumGenerated(7);
}
3

जनरेट केलेले अ‍ॅरे लीटकोड सोल्यूशनमध्ये जास्तीत जास्त मिळविण्यासाठी जावा कोड

import java.util.*;
import java.io.*;

class Main {

    public static int getMaximumGenerated(int n) {
        if(n == 0)return 0;
        if(n == 1)return 1;
        int[] tmp = new int[n+1];
        tmp[0] = 0;
        tmp[1] = 1;
        for(int i=1;i<=n;i++){
            if(2*i<=n)
                tmp[2*i] = tmp[i];
            if(2*i-1<=n)
                tmp[2*i-1] = tmp[i] + tmp[i-1];
        }
        int ans = 0;
        for(int i=0;i<=n;i++)
            ans = Math.max(tmp[i], ans);
        return ans;
    }

    public static void main(String[] args){
        System.out.println(getMaximumGenerated(7));
    }
}
3

गुंतागुंत विश्लेषण

वेळ कॉम्प्लेक्सिटी

ओ (एन), कारण आपण सर्व एन घटक तयार करतो.

स्पेस कॉम्प्लेक्सिटी

ओ (एन), कारण आम्ही अ‍ॅरे व्हॅल्यूज संचयित करण्यासाठी तात्पुरती अ‍ॅरे तयार केली आहेत.