ජනනය කරන ලද අරා ලීට්කෝඩ් විසඳුමෙන් උපරිම ලබා ගන්න


දුෂ්කරතා මට්ටම පහසු
අරා

උත්පාදනය කරන ලද අරා ලීට්කෝඩ් විසඳුමේ උපරිමය ලබා ගැනීමේ ගැටළුව අපට තනි සංඛ්‍යාවක් ලබා දී ඇත. දී ඇති තනි සමඟ නිඛිල, ජනනය කරන ලද අරාවෙහි උපරිම නිඛිලය සොයා ගැනීමට අපට අවශ්‍යය. අරාව පරම්පරාවට නීති කිහිපයක් තිබේ. පනවා ඇති සීමාවන් යටතේ, ජනනය කළ හැකි උපරිම නිඛිලය සොයා ගැනීමට අපට අවශ්‍යය. නීති:

  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) වන දර්ශකය සඳහා ජනනය කළ අගය අපට නොතිබෙනු ඇත. එවැනි අවස්ථාවකදී, ප්‍රති result ලය නිවැරදි නොවනු ඇත.

ගැටළුව විසඳීම සඳහා, අපි මූලද්රව්ය උත්පාදනය සඳහා සූත්රයන් හසුරුවන්නෙමු. 1 වන රීතියට අනුව, මම i-3 සමඟ ආදේශ කළහොත්. අර [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 මූලද්‍රව්‍ය ජනනය කරනවා.

අභ්‍යවකාශ සංකීර්ණතාව

මත), අරා අගයන් ගබඩා කිරීම සඳහා අපි තාවකාලික අරාවක් නිර්මාණය කළ නිසා.