Get Maximum in Generated Array
给一个数字n, 求n个数字组成的数组, 满足arr[0] = 0; arr[1] = 1; arr[偶数] = arr[偶数/2]; arr[奇数] = arr[奇数/2] + arr[奇数/2+1] 的最大数.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
class Solution { public int getMaximumGenerated(int n) { if(n == 0) return 0; if(n == 1) return 1; int[] arr = new int[n+1]; int res = 1; arr[0] = 0; arr[1] = 1; for(int i = 2; i <= n; i++) { if(i % 2 == 0) { arr[i] = arr[i / 2]; } else { arr[i] = arr[i / 2] + arr[(i / 2) + 1]; } res = Math.max(res, arr[i]); } return res; } } |