Untitled

 avatar
user_9132356
python
a year ago
491 B
3
Indexable
Never
def maxScore(popularity):
    
    n = len(popularity)
    
    def dfs(i, j, dp):
        if i >= n: return 0
        if dp[i][j] != -1:
            return dp[i][j]
        dp[i][j] = max(popularity[i]*j + dfs(i+1, j+1, dp), dfs(i+1, j, dp))
        return dp[i][j]
       
    dp = [[-1 for _ in range(n+1)] for _ in range(n+1)]
    satisfaction.sort()  # so that we can increase the value of satisfaction[i]*j bigger the satisafcation[i] the bigger j
    return dfs(0, 1, dp)