Python程式：在生成的陣列中查詢最大值

假設我們有一個數字 n。我們必須按照以下方式生成一個長度為 n + 1 的陣列 A：

  • A[0] = 0

  • A[1] = 1

  • A[2 * i] = A[i] 如果 2 <= 2 * i <= n

  • A[2 * i + 1] = A[i] + A[i + 1] 如果 2 <= 2 * i + 1 <= n

最後，我們必須找到陣列 nums 中的最大數字。

因此，如果輸入類似於 n = 5，則輸出將為 3，因為

  • A[0] = 0

  • A[1] = 1

  • A[2] = A[1] = 1

  • A[3] = A[1] + A[2] = 1 + 1 = 2

  • A[4] = A[2]= 1

  • A[5] = A[2] + A[3] = 1 + 2 = 3

  • A[6] = A[3] = 2

所以最大值為 3

為了解決這個問題，我們將遵循以下步驟：

  • A := 從 0 到 n 的一個新列表

  • 對於 A 中的每個元素 i，執行以下操作：

    • 如果 i 等於 0 或 i 等於 1，則

      • 轉到下一個迭代

    • 否則，當 i 為偶數時，則

      • A[i] := A[i/2 的整數部分]

    • 否則，

      • A[i] := A[i/2 的整數部分] + A[(i/2 的整數部分) + 1]

  • 返回 A 的最大元素

示例（Python）

讓我們看看以下實現，以便更好地理解：

 線上演示

def solve(n):
   A = list(range(0,n+1))
   for i in A:
      if i == 0 or i == 1:
         continue
      elif i%2 == 0:
         A[i] = A[i//2]
      else:
         A[i] = A[i//2] + A[(i//2) + 1]
   return max(A)

n = 5
print(solve(n))

輸入

5

輸出

3

更新於: 2021年5月17日

310 次檢視

開啟你的 職業生涯

完成課程獲得認證

立即開始
廣告