Python程式：查詢優秀子陣列的最大分數

假設我們有一個名為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 := (如果i > -1則為nums[i]，否則為-1)和(如果j < nums的大小則為nums[j]，否則為-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))

輸入

[2,5,4,8,5,6], 3

輸出

20

更新於：2021年10月8日

411 次瀏覽

啟動您的職業生涯

完成課程後獲得認證

開始
廣告