数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装学
法学Python程序：查找列表的最大最终幂
假设我们有一个列表，列表的幂定义为所有索引上 (index + 1) * value_at_index 的总和。或者，我们可以这样表示：
$$\displaystyle\sum\limits_{i=0}^{n-1} (i+1)\times list[i]$$
现在，我们有一个包含 N 个正整数的列表 nums。我们可以选择列表中的任何单个值，并将其移动（而不是交换）到任何位置，可以将其移到列表的开头或结尾。我们也可以选择根本不移动任何位置。我们必须找到列表的最大可能的最终幂。结果必须对 10^9 + 7 取模。
因此，如果输入类似于 nums = [4, 2, 1]，则输出将为 16。
为了解决这个问题，我们将遵循以下步骤：
P := [0]
base := 0
对于A中每个索引i和项目x，执行：
在P的末尾插入P[-1] + x
base := base + i * x
定义一个函数 eval_at()。这将需要 j, x
返回 -j * x + P[j]
定义一个函数 intersection()。这将需要 j1, j2
返回 (P[j2] - P[j1]) /(j2 - j1)
hull := [-1]
indexes := [0]
对于范围从1到P大小的j，执行：
当 hull 不为空且 intersection(indexes[-1], j) <= hull[-1] 时，执行：
删除hull的最后一个元素
删除indexes的最后一个元素
在hull的末尾插入intersection(indexes[-1], j)
在indexes的末尾插入j
ans := base
对于A中每个索引i和项目x，执行：
j := x可以在hull中插入的部分，保持排序顺序
j := max(j - 1, 0)
ans := max(ans, base + eval_at(i, x) - eval_at(indexes[j], x))
返回 ans mod (10^9 + 7)
示例
让我们看看下面的实现，以便更好地理解：
import bisect 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 def eval_at(j, x): return -j * x + P[j] def intersection(j1, j2): return (P[j2] - P[j1]) / (j2 - j1) hull = [-1] indexes = [0] for j in range(1, len(P)): while hull and intersection(indexes[-1], j) <= hull[-1]: hull.pop() indexes.pop() hull.append(intersection(indexes[-1], j)) indexes.append(j) ans = base for i, x in enumerate(A): j = bisect.bisect(hull, x) j = max(j - 1, 0) ans = max(ans, base + eval_at(i, x) - eval_at(indexes[j], x)) return ans % (10 ** 9 + 7) ob = Solution() print (ob.solve([4, 2, 1]))
输入
[4, 2, 1]
输出
16
173 次浏览
