ജനറേറ്റുചെയ്‌ത അറേ ലീറ്റ്‌കോഡ് പരിഹാരത്തിൽ പരമാവധി നേടുക


വൈഷമ്യ നില എളുപ്പമായ
അറേ

ജനറേറ്റഡ് അറേ ലീറ്റ്കോഡ് സൊല്യൂഷനിൽ പരമാവധി നേടുക എന്ന പ്രശ്നം ഞങ്ങൾക്ക് ഒരു പൂർണ്ണസംഖ്യ നൽകി. നൽകിയ സിംഗിൾ ഉപയോഗിച്ച് പൂർണ്ണസംഖ്യ, ജനറേറ്റുചെയ്‌ത അറേയിലെ പരമാവധി സംഖ്യ കണ്ടെത്തേണ്ടതുണ്ട്. അറേ ജനറേഷന് ചില നിയമങ്ങളുണ്ട്. അടിച്ചേൽപ്പിച്ച നിയന്ത്രണങ്ങൾക്ക് കീഴിൽ, ജനറേറ്റുചെയ്യാൻ കഴിയുന്ന പരമാവധി സംഖ്യ ഞങ്ങൾ കണ്ടെത്തേണ്ടതുണ്ട്. നിയമങ്ങൾ ഇവയാണ്:

  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
അക്കങ്ങൾ [(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 ആണ്.

ജനറേറ്റുചെയ്‌ത അറേ ലീറ്റ്‌കോഡ് പരിഹാരത്തിൽ പരമാവധി നേടുന്നതിനുള്ള സമീപനം

ജനറേറ്റുചെയ്‌ത അറേ ലീറ്റ്‌കോഡ് പരിഹാരത്തിൽ പരമാവധി നേടുക എന്ന പ്രശ്‌നത്തിന് ചില പരിമിതികളുണ്ട്, അത് തൃപ്‌തിപ്പെടുത്തേണ്ടതുണ്ട്. തന്നിരിക്കുന്ന പരിമിതികൾക്ക് കീഴിൽ, ഞങ്ങൾ പരമാവധി സംഖ്യ കണ്ടെത്തേണ്ടതുണ്ട്. അറേ ജനറേഷനായുള്ള നിയമങ്ങൾ പ്രശ്നത്തിന്റെ വിവരണത്തിൽ ഇതിനകം വിശദീകരിച്ചിട്ടുണ്ട്. മനസ്സിലേക്ക് വരുന്ന ആദ്യത്തെ രീതി അറേയുടെ ജനറേഷനും പരമാവധി ഘടകം കണ്ടെത്തലുമാണ്. എന്നാൽ അത് പ്രശ്നം പരിഹരിക്കുമോ?

തലമുറയുമായി ഞങ്ങൾ മുന്നോട്ട് പോയാൽ ഞങ്ങൾക്ക് ശരിയായ ഫലങ്ങൾ കണ്ടെത്താൻ കഴിയില്ല. കാരണം ഇത് ഞങ്ങൾ എങ്ങനെ ശ്രേണി സൃഷ്ടിക്കുന്നു എന്നതിനെ ആശ്രയിച്ചിരിക്കുന്നു. നമ്മൾ ith സൂചികയിലായിരിക്കുമ്പോൾ 2ith, (2i + 1) സൂചികയിൽ ഘടകങ്ങൾ സൃഷ്ടിക്കുകയാണെങ്കിൽ. ആ സമയത്ത്, (i + 1) th സൂചികയ്‌ക്കായി ജനറേറ്റുചെയ്‌ത മൂല്യം ഞങ്ങൾക്കില്ല. അത്തരം സന്ദർഭങ്ങളിൽ, ഫലം കൃത്യമായിരിക്കില്ല.

പ്രശ്നം പരിഹരിക്കുന്നതിന്, മൂലക ജനറേഷനായുള്ള സൂത്രവാക്യങ്ങൾ ഞങ്ങൾ കൈകാര്യം ചെയ്യും. മൂന്നാമത്തെ റൂളിൽ‌, ഞാൻ‌ i-1 ഉപയോഗിച്ച് മാറ്റിസ്ഥാപിക്കുകയാണെങ്കിൽ‌. arr [3 * i-2] = arr [i] + arr [i-1] എന്ന് ഞങ്ങൾ കണ്ടെത്തി. അതിനാൽ, ഇപ്പോൾ നമുക്ക് അറേ ജനറേഷനായി നിയമങ്ങൾ ഉപയോഗിക്കാം. കാരണം ഇതിനകം സൃഷ്ടിച്ച മൂല്യത്തിന്റെ മൂല്യം ഈ നിയമം ഉപയോഗിക്കുന്നു. ഭാവിയിൽ അജ്ഞാതമായ ഏതെങ്കിലും മൂല്യങ്ങൾ ഉപയോഗിക്കുന്നതിനുപകരം ഞങ്ങൾ മുൻകൂട്ടി കണക്കാക്കിയ മൂല്യങ്ങൾ ഉപയോഗിക്കുന്നു. ഇപ്പോൾ ഞങ്ങൾ ഫോർ ഫോർ ലൂപ്പ് ഉപയോഗിച്ച് മുഴുവൻ പ്രക്രിയയും അനുകരിക്കുകയും 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

സങ്കീർണ്ണത വിശകലനം

സമയ സങ്കീർണ്ണത

O (N), കാരണം ഞങ്ങൾ എല്ലാ n ഘടകങ്ങളും സൃഷ്ടിക്കുന്നു.

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

O (N), കാരണം അറേ മൂല്യങ്ങൾ സംഭരിക്കുന്നതിന് ഞങ്ങൾ ഒരു താൽക്കാലിക അറേ സൃഷ്ടിച്ചു.