一、题目

给你一个整数 n 。按下述规则生成一个长度为 n + 1 的数组 nums ：

  • nums[0] = 0
  • nums[1] = 1
  • 当 2 <= 2 i <= n 时，nums[2 i] = nums[i]
  • 当 2 <= 2 i + 1 <= n 时，nums[2 i + 1] = nums[i] + nums[i + 1]

返回生成数组 nums 中的 最大值。

点击查看原题
难度级别： 简单

二、思路

1）数组记录

根据数据规则，i位置的元素依赖于i/2位置或也依赖于i/2+1位置的元素
所以建立数组memo记录以及计算过的元素

三、代码

1）数组记录

  1. class Solution {
  2.     public int getMaximumGenerated(int n) {
  3.         if (n <= 1) {
  4.             return n;
  5.         }
  6.         int[] memo = new int[n+1];
  7.         memo[1] = 1;
  8.         int ans = 1;
  9.         for (int i = 2; i <= n; i++) {
  10.             if ((i&1) == 1) {
  11.                 memo[i] = memo[i >> 1] + memo[(i >> 1) + 1];
  12.             } else {
  13.                 memo[i] = memo[i >> 1];
  14.             }
  15.             ans = Math.max(ans, memo[i]);
  16.         }
  17.         return ans;
  18.     }
  19. }

时间复杂度为O(n)，空间复杂度为O(n)