数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究Python程序：查找子列表大小，使A的最小值与A的大小之积最大化
假设我们有一个名为nums的数字列表和另一个值pos。我们必须找到nums的一个子列表A，该子列表包含索引pos，使得(A的最小值) * (A的大小)最大化，然后返回该值。
因此，如果输入类似于nums = [-2, 2, 5, 4] pos = 3，则输出将为8，因为最佳子列表是[5, 4]，因为(5, 4) = 4，其大小为2，我们有4 * 2 = 8。
为了解决这个问题，我们将遵循以下步骤：
ans := A[pos]，m := A[pos]
i := pos，j := pos
对i从0到A的大小-1执行以下操作：
left := A[i - 1]（如果i - 1 >= 0，否则为-inf）
right := A[j + 1]（如果j + 1 < A的大小，否则为-inf）
如果left >= right，则
i := i - 1
m := m和A[i]的最小值
否则，
j := j + 1
m := m和A[j]的最小值
ans := ans和(m *(j - i + 1))的最大值
返回ans
示例
让我们看看下面的实现以获得更好的理解：
class Solution:
def solve(self, A, pos):
NINF = float("-inf")
ans = m = A[pos]
i = pos
j = pos
for _ in range(len(A) - 1):
left = A[i - 1] if i - 1 >= 0 else NINF
right = A[j + 1] if j + 1 < len(A) else NINF
if left >= right:
i -= 1
m = min(m, A[i])
else:
j += 1
m = min(m, A[j])
ans = max(ans, m * (j - i + 1))
return ans
ob = Solution()
nums = [-2, 2, 5, 4]
pos = 3
print(ob.solve(nums, pos))输入
[-2, 2, 5, 4], 3
输出
8
更新于: 2020年12月23日
102 次浏览
广告