Отримайте максимум у створеному масиві Leetcode Solution


Рівень складності Легко
масив

Проблема Get Maximum in Generated Array Leetcode Solution надала нам одне ціле число. З даним синглом ціле, нам потрібно знайти максимальне ціле число в сформованому масиві. Генерація масиву має деякі правила. Згідно з накладеними обмеженнями, нам потрібно знайти максимальне ціле число, яке могло бути сформовано. Правила такі:

  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

Але перед тим, як піти далі в розчин. Слід поглянути на кілька прикладів.

Отримайте максимум у створеному масиві Leetcode Solution

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

Отже, ми можемо бачити nums = [0,1,1,2,1,3,2,3], і максимум - 3 серед них. Таким чином, відповідь 3.

Підхід до отримання максимуму у створеному масиві Leetcode Solution

Проблема Отримати максимум у створеному масиві Leetcode Solution має деякі обмеження, які необхідно задовольнити. За даними обмеженнями нам потрібно знайти максимальне ціле число. Правила генерації масиву вже були пояснені в описі проблеми. Перший метод, який спадає на думку - це генерація масиву та пошук максимального елемента. Але чи вирішить це проблему?

Якщо ми просто продовжимо покоління, ми не зможемо знайти правильні результати. Тому що це залежить від того, як ми генеруємо масив. Якщо ми генеруємо елементи з 2-м і (2i + 1) індексом, коли ми знаходимось з i-м індексом. На той момент ми не мали б сформованого значення для (i + 1) -го індексу. У такому випадку результат буде неточним.

Для вирішення проблеми ми будемо маніпулювати формулами генерації елементів. Якщо замінити i на i-1, у 3-му правилі. ми знаходимо, що arr [2 * i-1] = arr [i] + arr [i-1]. Отже, тепер ми можемо використовувати правила генерації масивів. Оскільки це правило використовує значення вже створеного значення. Отже, замість використання будь-яких майбутніх невідомих значень ми використовуємо попередньо розраховані значення. Отже, ми просто моделюємо весь процес, використовуючи цикл for, і перевіряємо, чи 2 * i та 2 * i-1 знаходяться в межах масиву. Після підтвердження ми використовуємо формули для заповнення масиву.

код

Код C ++ для отримання максимуму в створеному масиві Leetcode Solution

#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

Java-код для отримання максимуму в створеному масиві Leetcode Solution

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), тому що ми створили тимчасовий масив для зберігання значень масиву.