資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究Python 列表元素重排獲取最大功率值程式
假設我們有一個包含 N 個正數的列表 nums。現在我們可以從列表中選擇任何單個值，並將其移動（而不是交換）到任何位置。我們也可以不將任何值移動到任何位置。所以我們必須找到列表可能的最大最終功率值是多少？眾所周知，列表的功率是所有索引 i 上 (index + 1) * value_at_index 的總和。
$$\displaystyle\sum\limits_{i=0}^{n-1} (i+1)\times list[i]$$
因此，如果輸入類似於 nums = [6, 2, 3]，則輸出將為 26，因為我們可以將 6 移動到末尾以獲得列表 [2, 3, 6]，因此功率為：(2 * 1) + (3 * 2) + (6 * 3) = 26。
為了解決這個問題，我們將遵循以下步驟 -
P := 一個值為 0 的列表
base := 0
對於 A 的每個索引 i 和值 x，執行
將 P 的最後一個元素 + x 插入到 P 的末尾
base := base + (i+1) * x
ans := base
對於 A 的每個索引 i 和值 x，執行
對於 j 從 0 到 A 的大小 + 1，執行
ans := ans 和 (base + P[i] - P[j] -(i - j) * x) 的最大值
返回 ans
示例
讓我們看看下面的實現以更好地理解 -
class Solution: def solve(self, A): P = [0] base = 0 for i, x in enumerate(A, 1): P.append(P[-1] + x) base += i * x ans = base for i, x in enumerate(A): for j in range(len(A) + 1): ans = max(ans, base + P[i] - P[j] - (i - j) * x) return ans ob = Solution() nums = [6, 2, 3] print(ob.solve(nums))
輸入
[6, 2, 3]
輸出
26
更新於: 2020-12-22
611 次瀏覽
廣告