首先本题可以抽象为从原数组中选出一些子数组，并让这些子数组的(i) * a[i]的和最大
解法：
将原数组从大到小排序
f[i] = i * a1 + (i-1) * a2 + ...
f[i-1] = (i-1) * a1 + (i-2)*a2 + ...
f[i] = f[i - 1] + (a1 + a2 + ....) //加上一个前缀和
class Solution: def maxSatisfaction(self, satisfaction: List[int]) -> int: f = 0 satisfaction.sort(reverse=True) for s in accumulate(satisfaction): if s <= 0: break f += s return f