Python程式：查詢旋轉陣列的最大加權和

假設我們有一個包含一些元素的陣列。我們需要找到如果陣列元素被旋轉後，其最大加權和是多少。陣列 nums 的加權和可以如下計算：

$$\mathrm{𝑆=\sum_{\substack{𝑖=1}}^{n}𝑖∗𝑛𝑢𝑚𝑠[𝑖]}$$

因此，如果輸入類似於 L = [5,3,4]，則輸出將為 26，因為

  • 陣列為 [5,3,4]，和為 5 + 2*3 + 3*4 = 5 + 6 + 12 = 23

  • 陣列為 [3,4,5]，和為 3 + 2*4 + 3*5 = 3 + 8 + 15 = 26（最大）

  • 陣列為 [4,5,3]，和為 4 + 2*5 + 3*3 = 4 + 10 + 9 = 23

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

  • n := nums 的大小
  • sum_a := nums 中所有元素的和
  • ans := 所有 (nums[i] *(i + 1)) 的元素之和，其中 i 的範圍從 0 到 n
  • cur_val := ans
  • 對於 i 的範圍從 0 到 n - 1，執行以下操作：
    • cur_val := cur_val - sum_a + nums[i] * n
    • ans := ans 和 cur_val 的最大值
  • 返回 ans

示例

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

def solve(nums):
    n = len(nums)
    sum_a = sum(nums)
    cur_val = ans = sum(nums[i] * (i + 1) for i in range(n))
   
    for i in range(n):
        cur_val = cur_val - sum_a + nums[i] * n
        ans = max(ans, cur_val)
   
    return ans

nums = [5,3,4]
print(solve(nums))

輸入

[5,3,4]

輸出

26

更新於： 2021年10月6日

158 次檢視

開啟你的 職業生涯

透過完成課程獲得認證

開始學習
廣告