Python에서 좋은 하위 배열의 최대 점수를 찾는 프로그램

<시간/>

nums라는 배열과 k 값이 있다고 가정합니다. 하위 배열의 점수(i, j)는 하위 배열 nums[i..j] * (j-i+1)의 최소값으로 정의됩니다. 이제 좋은 하위 배열은 i <=k <=j인 하위 배열입니다. 좋은 하위 배열의 가능한 최대 점수를 찾아야 합니다.

따라서 입력이 nums =[2,5,4,8,5,6] k =3과 같으면 최적의 하위 배열이 여기에 (1, 5) 있기 때문에 출력은 20이 되므로 최소 nums[1 ..5]는 4이므로 4*(5-1+1) =20

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

ans :=nums[k], minNum :=nums[k]
나는 :=k, j :=k
i> -1 또는 j <숫자 크기인 동안 수행
- 동안 i> -1 및 nums[i]>=minNum, do
  - 나는 :=나는 - 1
- while j <숫자와 숫자의 크기[j]>=minNum, do
  - j :=j + 1
- ans :=ans의 최대값 및 ((j - i - 1) * minNum)
- minNum :=(i> -1인 경우 -1인 경우 nums[i]) 및 (j <인 경우 -1인 경우 nums[j])
  의 최대값
반환

예시

더 나은 이해를 위해 다음 구현을 살펴보겠습니다.

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