Untitled
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)