Find Maximum Non-decreasing Array Length

Ссылки сюда (1) →

• Leetcode/find-maximum-non-decreasing-array-length

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)

[ Хронологический вид ]Комментарии

(нет элементов)

Войдите, чтобы комментировать.