Find Maximum Non-decreasing Array Length
Материал из DISCOPAL
class Solution: def findMaximumLength(self, nums: List[int]) -> int: nums+=[float('inf')] presum=[0]+list(accumulate(nums)) n = len(nums)-1 # Max upper seq dp = [0]*(n+2) # index l Integrate [l..i) bestLeft = [0]*(n+2) for i in range(n): # Compare of max i+=1 bestLeft[i] = max(bestLeft[i], bestLeft[i - 1]) # When merging nums[l, i), consider the next segment as [i, r). # Find the minimum `r` where the sum(nums[l, i)) <= sum(nums[i, r)). # Equivalently, prefix[i] - prefix[l] <= prefix[r] - prefix[i]. # => prefix[r] >= prefix[i] * 2 - prefix[l] # Therefore, we can binary search `prefix` to find the minimum `r`. l = bestLeft[i] # idx entry 2 * prefix[i] - prefix[l] in prefix r = bisect.bisect_left(presum, 2 * presum[i] - presum[l]) dp[i] = dp[l] + 1 bestLeft[r] = i return dp[n]
Решено: Evvnes 11:58, 16 сентября 2024 (UTC)
[ Хронологический вид ]Комментарии
Войдите, чтобы комментировать.