[leetcode] Reducing Dishes

Reducing Dishes

私の答え

1に計算された値は0より大きい.このように計算すると、[음수 499개, 0이나 양수 1개]が入ってきた時には完全に探索していたので、O(N 2)です.だから私はそうしたくない.🤔「困っています.

既存のコード

class Solution:
    def maxSatisfaction(self, satisfaction: List[int]) -> int:
        sortedSatisfaction = sorted(satisfaction)
        index, sum, maxSum = 0, 0, 0
        isLast = False
        
        while True:
            startValue = sortedSatisfaction[index]
            if startValue > 0:
                isLast = True
            for start in range(index, len(sortedSatisfaction)):
                sum += sortedSatisfaction[start] * (start-index+1)
            maxSum = max(maxSum, sum)
            sum = 0
            index += 1
            if index > len(sortedSatisfaction)-1 or isLast:
                break
        
        return maxSum

他人を解く

最も近い場合は,ソートされたsatisfactionで,大きな値を基準に左に加算し,負の数が現れる場合が先である.したがって,右から左に1つの値を加算して負数が現れると,その点の直前から全体満足度を算出する.始点が一番左(例えば[0,1,2, ...])でも、ドアを1回回れば計算できるので、O(N)はこの問題を解決することができる.
君がどうしてこれを知っているのか本当に分からない.コードを何度も見て、それを感じることができますか?🫥

改良されたコード

class Solution:
    def maxSatisfaction(self, satisfaction: List[int]) -> int:
        sortedSatisfaction = sorted(satisfaction)
        start = len(sortedSatisfaction) - 1
        sum = 0
        
        for index in range(start, -1, -1):
            sum += sortedSatisfaction[index]
            if sum < 0:
                break
            start -= 1
        
        start += 1
        sum = 0
        
        for index in range(start, len(sortedSatisfaction)):
            sum += sortedSatisfaction[index] * (index-start+1)
        
        return sum

参考資料

code Explainer