This is the 25th day of my participation in the August Genwen Challenge.More challenges in August

8.23 – 1646. Gets the maximum value in the generated array

The question

I give you an integer n. Generate an array nums of length n + 1 as follows:

Rule 1: Nums [0] = 0 Rule 2: NUMs [1] = 1 Rule 3: When 2 <= 2 * I <= n, NUMs [2 * I] = NUMs [I] When 2 <= 2 * I + 1 <= n, nums[2 * I + 1] = nums[I] + nums[I + 1] returns the maximum value in the generated array nums.

Example 1:

Enter n =7Output:3According to the rule: nums[0] = 0
  nums[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 = 3Therefore, nums = [0.1.1.2.1.3.2.3], maximum value3
Copy the code

Example 2:

Enter n =2Output:1Explanation: According to the rule, nums[0], nums [1] and nums [2The maximum value of] is1
Copy the code

Example 3:

Enter n =3Output:2Explanation: According to the rule, nums[0], nums [1], nums [2] and nums [3The maximum value of] is2
Copy the code

Analysis of the

There are two solutions to this problem

  • The numS array is generated in a loop, and then the last value in ascending order is the maximum, and the last item in the array is returned
  • In the loop, the value of each item is compared to Max. If the value is greater than Max, the value of Max is assigned. Finally, the value of Max can be returned

Odd numbers are added to the array according to rule 3, even numbers are added to the array according to rule 4

Plan a

var getMaximumGenerated = function (n) {
  let nums = [0.1];
  if (n < 2) return nums[n];
    
  for (let i = 2; i <= n; i++) {
    let mutilple = Math.floor(i / 2);
    if (i % 2= = =0) {
      nums[2 * mutilple] = nums[mutilple];
    }
    if (i % 2= = =1) {
      nums[2 * mutilple + 1] = nums[mutilple] + nums[mutilple + 1]; }}let sortArr = nums.sort((a , b) = > {
      return a - b
  })
  return sortArr[sortArr.length - 1]};Copy the code

Scheme 2

var getMaximumGenerated = function (n) {
  let nums = [0.1];
  let max = 0;
  if (n < 2) return nums[n];
  for (let i = 2; i <= n; i++) {
    let mutilple = Math.floor(i / 2);
    if (i % 2= = =0 ) {
        nums[2 * mutilple] = nums[mutilple]
        if (nums[2 * mutilple] > max) max = nums[2 * mutilple]
    }
    if (i % 2= = =1) {
        nums[2 * mutilple + 1] = nums[mutilple] + nums[mutilple + 1]
        if (nums[2 * mutilple + 1] > max) max = nums[2 * mutilple + 1]}}return max;
};
Copy the code

conclusion

😂 why is the memory consumption so large? Change the way also big!!