ਤਿਆਰ ਕੀਤੇ ਐਰੇ ਲੀਟਕੋਡ ਘੋਲ ਵਿੱਚ ਵੱਧ ਤੋਂ ਵੱਧ ਪ੍ਰਾਪਤ ਕਰੋ


ਮੁਸ਼ਕਲ ਪੱਧਰ ਸੌਖੀ
ਅਰੇ

ਸਮੱਸਿਆ ਪੈਦਾ ਹੋਣ ਵਾਲੀ ਐਰੇ ਲੀਟਕੋਡ ਸਲਿ .ਸ਼ਨ ਵਿਚ ਅਧਿਕਤਮ ਪ੍ਰਾਪਤ ਕਰੋ ਸਾਨੂੰ ਇਕੋ ਪੂਰਨ ਅੰਕ ਪ੍ਰਦਾਨ ਕਰਦਾ ਹੈ. ਦਿੱਤੇ ਸਿੰਗਲ ਦੇ ਨਾਲ ਪੂਰਨ ਅੰਕ, ਸਾਨੂੰ ਤਿਆਰ ਕੀਤੀ ਐਰੇ ਵਿਚ ਵੱਧ ਤੋਂ ਵੱਧ ਪੂਰਨ ਅੰਕ ਲੱਭਣ ਦੀ ਜ਼ਰੂਰਤ ਹੈ. ਐਰੇ ਪੀੜ੍ਹੀ ਦੇ ਕੁਝ ਨਿਯਮ ਹਨ. ਲਗਾਈਆਂ ਗਈਆਂ ਰੁਕਾਵਟਾਂ ਦੇ ਤਹਿਤ, ਸਾਨੂੰ ਵੱਧ ਤੋਂ ਵੱਧ ਪੂਰਨ ਅੰਕ ਲੱਭਣ ਦੀ ਜ਼ਰੂਰਤ ਹੈ ਜੋ ਤਿਆਰ ਕੀਤੀ ਜਾ ਸਕਦੀ ਹੈ. ਨਿਯਮ ਇਹ ਹਨ:

  1. ਅਰਰ [0] = 0, ਅਰਰ [1] = 1
  2. arr [2 * i] = arr [i] ਜਿੱਥੇ 2 <= 2 * i <= n
  3. ਅਤੇ ਅਰਰ [2 * i + 1] = ਅਰਰ [i] + ਅਰਰ [i + 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 ਹੈ.

ਤਿਆਰ ਕੀਤੇ ਐਰੇ ਲੀਟਕੋਡ ਸਲਿ .ਸ਼ਨ ਵਿੱਚ ਵੱਧ ਤੋਂ ਵੱਧ ਪ੍ਰਾਪਤ ਕਰਨ ਲਈ ਪਹੁੰਚ

ਵੱਧ ਤੋਂ ਵੱਧ ਪ੍ਰਾਪਤ ਕੀਤੀ ਐਰੇ ਲੀਟਕੋਡ ਸਲਿ Theਸ਼ਨ ਵਿੱਚ ਸਮੱਸਿਆ ਕੁਝ ਸਮੱਸਿਆਵਾਂ ਹਨ ਜਿਹਨਾਂ ਨੂੰ ਸੰਤੁਸ਼ਟ ਹੋਣਾ ਚਾਹੀਦਾ ਹੈ. ਦਿੱਤੀਆਂ ਗਈਆਂ ਰੁਕਾਵਟਾਂ ਦੇ ਤਹਿਤ, ਸਾਨੂੰ ਵੱਧ ਤੋਂ ਵੱਧ ਪੂਰਨ ਅੰਕ ਲੱਭਣ ਦੀ ਲੋੜ ਹੈ. ਐਰੇ ਪੀੜ੍ਹੀ ਲਈ ਨਿਯਮ ਪਹਿਲਾਂ ਹੀ ਸਮੱਸਿਆ ਦੇ ਵੇਰਵੇ ਵਿੱਚ ਵਿਖਿਆਨ ਕੀਤੇ ਜਾ ਚੁੱਕੇ ਹਨ. ਪਹਿਲਾ methodੰਗ ਜੋ ਮਨ ਵਿਚ ਆਉਂਦਾ ਹੈ ਉਹ ਹੈ ਐਰੇ ਦੀ ਪੀੜ੍ਹੀ ਅਤੇ ਵੱਧ ਤੋਂ ਵੱਧ ਤੱਤ ਲੱਭਣਾ. ਪਰ ਕੀ ਇਹ ਸਮੱਸਿਆ ਹੱਲ ਹੋਏਗੀ?

ਜੇ ਅਸੀਂ ਸਧਾਰਣ ਤੌਰ 'ਤੇ ਪੀੜ੍ਹੀ ਨਾਲ ਅੱਗੇ ਵਧਦੇ ਹਾਂ ਤਾਂ ਅਸੀਂ ਸਹੀ ਨਤੀਜੇ ਨਹੀਂ ਲੱਭ ਸਕਾਂਗੇ. ਕਿਉਂਕਿ ਇਹ ਨਿਰਭਰ ਕਰਦਾ ਹੈ ਕਿ ਅਸੀਂ ਐਰੇ ਕਿਵੇਂ ਤਿਆਰ ਕਰਦੇ ਹਾਂ. ਜੇ ਅਸੀਂ 2ith ਅਤੇ (2i + 1) ਇੰਡੈਕਸ ਤੇ ਤੱਤ ਤਿਆਰ ਕਰਦੇ ਹਾਂ ਜਦੋਂ ਅਸੀਂ ਆਈਥ ਇੰਡੈਕਸ 'ਤੇ ਹੁੰਦੇ ਹਾਂ. ਉਸ ਪਲ, ਸਾਡੇ ਕੋਲ (i + 1) ਵੇਂ ਇੰਡੈਕਸ ਦਾ ਤਿਆਰ ਮੁੱਲ ਨਹੀਂ ਹੋਵੇਗਾ. ਉਸ ਸਥਿਤੀ ਵਿੱਚ, ਨਤੀਜਾ ਸਹੀ ਨਹੀਂ ਹੋਵੇਗਾ.

ਸਮੱਸਿਆ ਨੂੰ ਹੱਲ ਕਰਨ ਲਈ, ਅਸੀਂ ਤੱਤ ਪੀੜ੍ਹੀ ਲਈ ਫਾਰਮੂਆਂ ਵਿੱਚ ਹੇਰਾਫੇਰੀ ਕਰਾਂਗੇ. ਜੇ ਅਸੀਂ 1 ਨੂੰ ਨਿਯਮ ਵਿੱਚ, i-3 ਨਾਲ i ਨੂੰ ਤਬਦੀਲ ਕਰਦੇ ਹਾਂ. ਸਾਨੂੰ ਉਹ ਆਰਰ ਮਿਲਿਆ ਹੈ [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

ਜਟਿਲਤਾ ਵਿਸ਼ਲੇਸ਼ਣ

ਟਾਈਮ ਜਟਿਲਤਾ

ਓ (ਐਨ), ਕਿਉਂਕਿ ਅਸੀਂ ਸਾਰੇ ਐੱਨ ਐਲੀਮੈਂਟਸ ਤਿਆਰ ਕਰਦੇ ਹਾਂ.

ਸਪੇਸ ਦੀ ਜਟਿਲਤਾ

ਓ (ਐਨ), ਕਿਉਂਕਿ ਅਸੀਂ ਐਰੇ ਵੈਲਯੂਜ਼ ਨੂੰ ਸਟੋਰ ਕਰਨ ਲਈ ਆਰਜ਼ੀ ਐਰੇ ਬਣਾਈ ਹੈ.