用 Python 编写程序来查找好子数组的最大得分

pythonserver side programmingprogramming更新于 2025/12/14 2:20:17

假设我们有一个名为 nums 的数组和一个值 k。考虑子数组 (i, j) 的得分定义为子数组 nums[i..j] * (j-i+1) 的最小值。现在，好子数组是 i <= k <= j 的子数组。我们必须找到一个好的子数组的最大可能分数。

因此，如果输入为 nums = [2,5,4,8,5,6] k = 3，则输出将为 20，因为最佳子数组在这里 (1, 5)，因此 nums[1..5] 的最小值为 4，因此 4*(5-1+1) = 20

为了解决这个问题，我们将遵循以下步骤 −

ans := nums[k], minNum := nums[k]
i := k, j := k
当 i > -1 或 j < nums 的大小时，执行
- 当 i > -1 且 nums[i] >= minNum，则执行
  - i := i - 1
- 当 j < nums 的大小且 nums[j] >= minNum 时，则执行
  - j := j + 1
- ans := ans 和 ((j - i - 1) * minNum) 的最大值
- minNum := (nums[i] if i > -1 否则为 -1) 和 (nums[j] if j < nums 的大小否则为 -1) 的最大值
返回 ans

示例

让我们看看下面的实现以便更好地理解

def solve(nums, k):
   ans = nums[k]
   minNum = nums[k]
   i = k
   j = k
   while i > -1 or j < len(nums):
      while i > -1 and nums[i] >= minNum:
         i -= 1
      while j < len(nums) and nums[j] >= minNum:
         j += 1
      ans = max(ans, (j - i - 1) * minNum)
      minNum = max(nums[i] if i > -1 else -1 , nums[j] if j <
len(nums) else -1)
   return ans

nums = [2,5,4,8,5,6]
k = 3
print(solve(nums, k))