1646. Get Maximum in Generated Array

links: Algorithms MOC

---

Get Maximum in Generated Array

Problem:

You are given an integer n. A 0-indexed integer array nums of length n + 1 is generated in the following way:

• nums[0] = 0
• nums[1] = 1
• nums[2 * i] = nums[i] when 2 <= 2 * i <= n
• nums[2 * i + 1] = nums[i] + nums[i + 1] when 2 <= 2 * i + 1 <= n

Return the maximum integer in the array nums

Constraints:

• 0 <= n <= 100

Thought Process:

1. You just have to loop through half of the n to generate the array, because nums[i] = nums[2 * i] which means nums[n] = nums[n / 2]
2. You will reach the end solution by solving smaller problems which is dynamic programming (if the n is 100, you have to calculate the indices before something like how fibonacci is solved)
3. Consider the edge case when n is 0

/**
 * @param {number} n
 * @return {number}
 */
var getMaximumGenerated = function(n) {
    if(n === 0) {
        return 0
    }
 
    let array = new Array(n)
    
    array[0] = 0;
    array[1] = 1;
 
    let result = Math.max(...n)
 
    // loop length will be half of array and if it's odd add 1
    // you can even use ceil
    let loopLength = Math.floor(n / 2) + n % 2
 
    for(let i = 0; i < loopLength; i++) {
        array[2 * i] = array[i]
        array[(2 * i) + 1] = array[i] + array[i + 1]
    }
 
    return Math.max(...array)
};

---

tags: array dynamic-programming simulation

sources:

• Get Maximum in Generated Array