ໄດ້ຮັບສູງສຸດໃນການຜະລິດ Array Leetcode Solution


ລະດັບຄວາມຫຍຸ້ງຍາກ Easy
Array

ບັນຫາໄດ້ຮັບສູງສຸດໃນການຜະລິດ Array Leetcode Solution ໃຫ້ພວກເຮົາມີເລກເຕັມດຽວ. ກັບໂສດທີ່ໃຫ້ integer, ພວກເຮົາຕ້ອງການຊອກຫາເລກເຕັມສູງສຸດໃນອາເລທີ່ຜະລິດ. ການຜະລິດອາເລມີກົດລະບຽບບາງຢ່າງ. ພາຍໃຕ້ຂໍ້ ຈຳ ກັດທີ່ ກຳ ນົດໄວ້, ພວກເຮົາ ຈຳ ເປັນຕ້ອງຊອກຫາຕົວເລກສູງສຸດທີ່ສາມາດຜະລິດໄດ້. ກົດລະບຽບແມ່ນ:

  1. arr [0] = 0, ມາຮອດ [1] = 1
  2. arr [2 * i] = arr [i] ບ່ອນທີ່ 2 <= 2 * i <= n
  3. ແລະມາຮອດ [2 * i + 1] = ມາຮອດ [i] + ຮອດ [i + 1] ບ່ອນທີ່ 2 <= 2 * i + 1 <= n

ແຕ່ກ່ອນທີ່ຈະ ດຳ ນ້ ຳ ຕື່ມອີກໃນວິທີແກ້ໄຂ. ພວກເຮົາຄວນຈະພິຈາລະນາບາງຕົວຢ່າງ.

ໄດ້ຮັບສູງສຸດໃນການຜະລິດ Array Leetcode Solution

n = 7
3

ຄຳ ອະທິບາຍ: ອີງຕາມກົດລະບຽບທີ່ໃຫ້ໄວ້:
nums [0] = 0, ເລກ [1] = 1
nums [(1 * 2) = 2] = ຕົວເລກ [1] = 1
nums [(1 * 2) + 1 = 3] = ຕົວເລກ [1] + ຕົວເລກ [2] = 1 + 1 = 2
nums [(2 * 2) = 4] = ຕົວເລກ [2] = 1
nums [(2 * 2) + 1 = 5] = ຕົວເລກ [2] + ຕົວເລກ [3] = 1 + 2 = 3
nums [(3 * 2) = 6] = ຕົວເລກ [3] = 2
nums [(3 * 2) + 1 = 7] = ຕົວເລກ [3] + ຕົວເລກ [4] = 2 + 1 = 3

ດັ່ງນັ້ນ, ພວກເຮົາສາມາດເຫັນຕົວເລກ = [0,1,1,2,1,3,2,3], ແລະສູງສຸດແມ່ນ 3 ໃນນັ້ນ. ສະນັ້ນ ຄຳ ຕອບແມ່ນ 3.

ວິທີການເພື່ອໃຫ້ໄດ້ຮັບສູງສຸດໃນການຜະລິດ Array Leetcode Solution

ບັນຫາໄດ້ຮັບສູງສຸດໃນການຜະລິດ Array Leetcode Solution ມີຂໍ້ ຈຳ ກັດບາງຢ່າງທີ່ຕ້ອງໄດ້ຮັບຄວາມພໍໃຈ. ພາຍໃຕ້ຂໍ້ ຈຳ ກັດດັ່ງກ່າວ, ພວກເຮົາ ຈຳ ເປັນຕ້ອງຊອກຫາເລກເຕັມສູງສຸດ. ກົດລະບຽບ ສຳ ລັບການຜະລິດຂບວນໄດ້ຖືກອະທິບາຍແລ້ວໃນ ຄຳ ອະທິບາຍຂອງບັນຫາ. ວິທີການ ທຳ ອິດທີ່ມາສູ່ຈິດໃຈແມ່ນການຜະລິດອາເລແລະຊອກຫາອົງປະກອບສູງສຸດ. ແຕ່ມັນຈະແກ້ໄຂບັນຫາໄດ້ບໍ?

ຖ້າພວກເຮົາພຽງແຕ່ສືບຕໍ່ເດີນ ໜ້າ ກັບລຸ້ນຄົນພວກເຮົາຈະບໍ່ສາມາດຫາຜົນໄດ້ຮັບທີ່ຖືກຕ້ອງ. ເນື່ອງຈາກວ່າມັນຂື້ນກັບວິທີທີ່ພວກເຮົາສ້າງອາເລ. ຖ້າພວກເຮົາຜະລິດອົງປະກອບຢູ່ທີ່ 2ith ແລະ (2i + 1) ດັດຊະນີເມື່ອພວກເຮົາຢູ່ໃນດັດຊະນີ ith. ໃນປັດຈຸບັນ, ພວກເຮົາຈະບໍ່ມີມູນຄ່າທີ່ຜະລິດ ສຳ ລັບ (i + 1) ດັດຊະນີ. ໃນກໍລະນີດັ່ງກ່າວ, ຜົນໄດ້ຮັບຈະບໍ່ຖືກຕ້ອງ.

ເພື່ອແກ້ໄຂບັນຫາ, ພວກເຮົາຈະ ໝູນ ໃຊ້ສູດ ສຳ ລັບການຜະລິດອົງປະກອບ. ຖ້າພວກເຮົາປ່ຽນ i ດ້ວຍ 1-i, ໃນກົດລະບຽບທີ 3. ພວກເຮົາພົບວ່າມາຮອດ [2 * i-1] = arr [i] + arr [i-1]. ສະນັ້ນ, ດຽວນີ້ພວກເຮົາສາມາດ ນຳ ໃຊ້ກົດລະບຽບ ສຳ ລັບການຜະລິດອາເລ. ເພາະວ່າກົດລະບຽບນີ້ໃຊ້ຄຸນຄ່າຂອງມູນຄ່າທີ່ຜະລິດແລ້ວ. ດັ່ງນັ້ນໃນທີ່ນີ້ແທນທີ່ຈະ ນຳ ໃຊ້ຄ່າທີ່ບໍ່ຮູ້ໃນອະນາຄົດພວກເຮົາ ກຳ ລັງໃຊ້ຄຸນຄ່າທີ່ໄດ້ ຄຳ ນວນໄວ້ລ່ວງ ໜ້າ. ດັ່ງນັ້ນຕອນນີ້ພວກເຮົາພຽງແຕ່ ຈຳ ລອງຂັ້ນຕອນທັງ ໝົດ ໂດຍໃຊ້ loop ແລະກວດເບິ່ງວ່າ 2 * i ແລະ 2 * i-1 ຢູ່ໃນຂອບເຂດຂອງອາເລ. ເມື່ອໄດ້ຮັບການຢັ້ງຢືນແລ້ວ, ພວກເຮົາໃຊ້ສູດເພື່ອຕື່ມຂໍ້ມູນໃສ່ແຖວ.

ລະຫັດ

ລະຫັດ C ++ ສຳ ລັບຮັບສູງສຸດໃນການຜະລິດ Array 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 ສຳ ລັບຮັບສູງສຸດໃນການຜະລິດ Array 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

ການວິເຄາະຄວາມສັບສົນ

ຄວາມສັບສົນເວລາ

ໂອ (N), ເນື່ອງຈາກວ່າພວກເຮົາສ້າງທັງ ໝົດ ຂອງ n ອົງປະກອບ.

ຄວາມສັບສົນໃນອະວະກາດ

ໂອ (N), ເພາະວ່າພວກເຮົາໄດ້ສ້າງ array ຊົ່ວຄາວເພື່ອເກັບຄ່າຄ່າ array.