జనరేటెడ్ అర్రే లీట్‌కోడ్ సొల్యూషన్‌లో గరిష్టంగా పొందండి


కఠినత స్థాయి సులువు
అర్రే

జనరేటెడ్ అర్రే లీట్‌కోడ్ సొల్యూషన్‌లో గరిష్టంగా పొందండి అనే సమస్య మాకు ఒకే పూర్ణాంకాన్ని అందించింది. ఇచ్చిన సింగిల్‌తో పూర్ణ సంఖ్య, మేము సృష్టించిన శ్రేణిలో గరిష్ట పూర్ణాంకాన్ని కనుగొనాలి. శ్రేణి తరం కొన్ని నియమాలను కలిగి ఉంది. విధించిన పరిమితుల క్రింద, మేము ఉత్పత్తి చేయగల గరిష్ట పూర్ణాంకాన్ని కనుగొనాలి. నియమాలు:

  1. arr [0] = 0, arr [1] = 1
  2. arr [2 * i] = arr [i] ఇక్కడ 2 <= 2 * i <= n
  3. మరియు arr [2 * i + 1] = arr [i] + arr [i + 1] ఇక్కడ 2 <= 2 * i + 1 <= n

కానీ ద్రావణంలో డైవింగ్ చేయడానికి ముందు. మేము కొన్ని ఉదాహరణలను పరిశీలించాలి.

జనరేటెడ్ అర్రే లీట్‌కోడ్ సొల్యూషన్‌లో గరిష్టంగా పొందండి

n = 7
3

వివరణ: ఇచ్చిన నిబంధనల ప్రకారం:
సంఖ్యలు [0] = 0, సంఖ్యలు [1] = 1
nums [(1 * 2) = 2] = nums [1] = 1
nums [(1 * 2) + 1 = 3] = nums [1] + nums [2] = 1 + 1 = 2
nums [(2 * 2) = 4] = nums [2] = 1
nums [(2 * 2) + 1 = 5] = nums [2] + nums [3] = 1 + 2 = 3
nums [(3 * 2) = 6] = nums [3] = 2
nums [(3 * 2) + 1 = 7] = nums [3] + nums [4] = 2 + 1 = 3

కాబట్టి, మనం సంఖ్యలు = [0,1,1,2,1,3,2,3] చూడవచ్చు మరియు వాటిలో గరిష్టంగా 3 ఉంటుంది. అందువలన సమాధానం 3.

జనరేటెడ్ అర్రే లీట్‌కోడ్ సొల్యూషన్‌లో గరిష్టంగా పొందే విధానం

జనరేటెడ్ అర్రే లీట్‌కోడ్ సొల్యూషన్‌లో గరిష్టంగా పొందే సమస్య సంతృప్తికరంగా ఉండాలి. ఇచ్చిన పరిమితుల క్రింద, మేము గరిష్ట పూర్ణాంకాన్ని కనుగొనవలసి ఉంటుంది. శ్రేణి ఉత్పత్తికి సంబంధించిన నియమాలు సమస్య యొక్క వివరణలో ఇప్పటికే వివరించబడ్డాయి. గుర్తుకు వచ్చే మొదటి పద్ధతి శ్రేణి యొక్క తరం మరియు గరిష్ట మూలకాన్ని కనుగొనడం. కానీ అది సమస్యను పరిష్కరిస్తుందా?

మేము తరంతో ముందుకు సాగితే సరైన ఫలితాలను కనుగొనలేము. ఎందుకంటే ఇది మేము శ్రేణిని ఎలా ఉత్పత్తి చేస్తాం అనే దానిపై ఆధారపడి ఉంటుంది. మనం ith సూచికలో ఉన్నప్పుడు 2ith మరియు (2i + 1) సూచిక వద్ద మూలకాలను ఉత్పత్తి చేస్తే. ఆ సమయంలో, మనకు (i + 1) వ సూచిక కోసం ఉత్పత్తి చేయబడిన విలువ ఉండదు. అలాంటప్పుడు, ఫలితం ఖచ్చితమైనది కాదు.

సమస్యను పరిష్కరించడానికి, మేము మూలకం ఉత్పత్తి కోసం సూత్రాలను తారుమారు చేస్తాము. 1 వ నియమం ప్రకారం, నేను i-3 తో భర్తీ చేస్తే. ఆ arr [2 * i-1] = arr [i] + arr [i-1] అని మేము కనుగొన్నాము. కాబట్టి, ఇప్పుడు మనం శ్రేణి ఉత్పత్తి కోసం నియమాలను ఉపయోగించవచ్చు. ఎందుకంటే ఈ నియమం ఇప్పటికే ఉత్పత్తి చేసిన విలువ యొక్క విలువను ఉపయోగిస్తుంది. భవిష్యత్తులో తెలియని విలువలను ఉపయోగించకుండా ఇక్కడ మనం ముందుగా లెక్కించిన విలువలను ఉపయోగిస్తున్నాము. కాబట్టి ఇప్పుడు మనం మొత్తం ప్రక్రియను ఒక ఫర్ లూప్ ఉపయోగించి అనుకరిస్తాము మరియు 2 * i మరియు 2 * i-1 శ్రేణి యొక్క సరిహద్దుల్లో ఉన్నాయా అని తనిఖీ చేస్తాము. ఇది ధృవీకరించబడిన తర్వాత, మేము శ్రేణిని పూరించడానికి సూత్రాలను ఉపయోగిస్తాము.

కోడ్

జనరేటెడ్ అర్రే లీట్‌కోడ్ సొల్యూషన్‌లో గరిష్టంగా పొందండి కోసం సి ++ కోడ్

#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

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

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

పై), ఎందుకంటే మేము అన్ని n మూలకాలను ఉత్పత్తి చేస్తాము.

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

పై), ఎందుకంటే శ్రేణి విలువలను నిల్వ చేయడానికి మేము తాత్కాలిక శ్రేణిని సృష్టించాము.