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 次瀏覽

開啟你的職業生涯

透過完成課程獲得認證

開始學習
廣告