באַקומען מאַקסימום אין דזשענערייטאַד עריי לעעטקאָדע לייזונג


שוועריקייט לעוועל גרינג
מענגע

דער פּראָבלעם באַקומען מאַקסימום אין גענעראַטעד עריי לעעטקאָדע סאַלושאַן צוגעשטעלט אַ איין ינטאַדזשער. מיט די געגעבן איין ינטעגער, מיר דאַרפֿן צו געפֿינען די מאַקסימום גאַנץ נומער אין די דזשענערייטאַד מענגע. די דור פון די מענגע האט עטלעכע כּללים. אונטער די ימפּאָוזד קאַנסטריינץ, מיר דאַרפֿן צו געפֿינען די מאַקסימום ינטאַדזשער וואָס קען זיין דזשענערייטאַד. די כּללים זענען:

  1. אַרר [0] = 0, אַרר [1] = 1
  2. אַרר [2 * איך] = אַרר [איך] ווו 2 <= 2 * איך <= ן
  3. און אַרר [2 * איך + 1] = אַרר [איך] + אַרר [איך + 1] ווו 2 <= 2 * איך + 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.

צוגאַנג צו באַקומען מאַקסימום אין דזשענערייטאַד עריי לעעטקאָדע לייזונג

דער פּראָבלעם באַקומען מאַקסימום אין דזשענערייטאַד עריי לעעטקאָדע סאַלושאַן האט עטלעכע קאַנסטריינץ וואָס מוזן זיין צופֿרידן. אונטער די געגעבן קאַנסטריינץ, מיר דאַרפֿן צו געפֿינען די מאַקסימום גאַנץ נומער. די כּללים פֿאַר די מענגע דור זענען שוין דערקלערט אין די באַשרייַבונג פון די פּראָבלעם. דער ערשטער אופֿן וואָס קומט צו גייַסט איז די דור פון מענגע און געפֿינען די מאַקסימום עלעמענט. אָבער וועט דאָס סאָלווע די פּראָבלעם?

אויב מיר פשוט פאָרזעצן דעם דור, מיר קענען נישט געפֿינען ריכטיק רעזולטאַטן. ווייַל עס דעפּענדס אויף ווי מיר דזשענערייט די מענגע. אויב מיר דזשענערייט עלעמענטן ביי 2 יט און (2 י + 1) אינדעקס ווען מיר זענען ביי יט אינדעקס. אין דעם מאָמענט, מיר וואָלט נישט האָבן די דזשענערייטאַד ווערט פֿאַר (i + 1) טה אינדעקס. אין דעם פאַל, דער רעזולטאַט וועט נישט זיין פּינטלעך.

צו סאָלווע די פּראָבלעם מיר מאַניפּולירן די פאָרמולאַס פֿאַר עלעמענט דור. אויב מיר פאַרבייַטן איך מיט איך -1, אין די 3 הערשן. מיר געפֿינען אַז אַרר [2 * איך -1] = אַרר [איך] + אַרר [איך -1]. איצט מיר קענען נוצן די כּללים פֿאַר מענגע דור. ווייַל דעם הערשן ניצט די ווערט פון שוין דזשענערייטאַד ווערט. דאָ אַנשטאָט פון ניצן קיין צוקונפֿט אומבאַקאַנט וואַלועס, מיר נוצן די פּרי-קאַלקיאַלייטיד וואַלועס. איצט מיר סימולירן דעם גאַנצן פּראָצעס מיט אַ for loop און קאָנטראָלירן אויב 2 * i און 2 * i-1 זענען אין די גווול פון די מענגע. אַמאָל דאָס איז באשטעטיקט, מיר נוצן די פאָרמולאַס צו פּלאָמבירן די מענגע.

קאָדעקס

C ++ קאָד פֿאַר באַקומען מאַקסימום אין דזשענערייטאַד עריי לעעטקאָדע סאַלושאַן

#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), ווייַל מיר דזשענערייט אַלע די N עלעמענטן.

ספעיס קאַמפּלעקסיטי

אָ (N), ווייַל מיר באשאפן אַ צייַטווייַליק מענגע צו קראָם די מענגע וואַלועס.