A chef has collected data on the satisfaction level of his n dishes. Chef can cook any dish in 1 unit of time.
Like-time coefficient of a dish is defined as the time taken to cook that dish including previous dishes multiplied by its satisfaction level  i.e.  time[i]*satisfaction[i]
Return the maximum sum of Like-time coefficient that the chef can obtain after dishes preparation.
Dishes can be prepared in any order and the chef can discard some dishes to get this maximum value.
 
Example 1:
Input: satisfaction = [-1,-8,0,5,-9]
Output: 14
Explanation: After Removing the second and last dish, the maximum total Like-time coefficient will be equal to (-1*1 + 0*2 + 5*3 = 14). Each dish is prepared in one unit of time.
Example 2:
Input: satisfaction = [4,3,2]
Output: 20
Explanation: Dishes can be prepared in any order, (2*1 + 3*2 + 4*3 = 20)

Example 3:
Input: satisfaction = [-1,-4,-5]
Output: 0
Explanation: People don't like the dishes. No dish is prepared.

Example 4:
Input: satisfaction = [-2,5,-1,0,3,-3]
Output: 35

 
Constraints:

n == satisfaction.length
1 <= n <= 500
-10^3 <= satisfaction[i] <= 10^3

Source: leetcode | Difficulty: MEDIUM
Tags: Dynamic programming

Sorting

Data structures

Greedy algorithms

Starter code: class Solution:
    def maxSatisfaction(self, satisfaction: List[int]) -> int:
        

Solutions:
class Solution:

	def maxSatisfaction(self, satisfaction: List[int]) -> int:
		satisfaction.sort()
		(total, res) = (0, 0)
		while satisfaction and satisfaction[-1] + total > 0:
			total += satisfaction.pop()
			res += total
		return res


class Solution:

	def maxSatisfaction(self, satisfaction: List[int]) -> int:
		satisfaction.sort()
		s = 0
		counter = 1
		for i in satisfaction:
			s += i * counter
			counter += 1
		check = s
		longest = s
		while True:
			s = 0
			counter = 1
			for i in satisfaction:
				s += i * counter
				counter += 1
			if s < check:
				return check
			if s > check:
				longest = s
			check = s
			if len(satisfaction) == 0:
				return longest
			del satisfaction[0]


class Solution:

	def maxSatisfaction(self, sat: List[int]) -> int:
		sat.sort()
		split = 0
		while split < len(sat) and sat[split] < 0:
			split += 1
		if split == len(sat):
			return 0
		(cur_sum, i, unit) = (0, 1, 0)
		for x in sat[split:]:
			cur_sum += i * x
			unit += x
			i += 1
		self.max = cur_sum
		for i in range(split - 1, -1, -1):
			(r, diff, psum) = (1, 0, cur_sum)
			for j in range(i, split):
				diff += r * sat[j]
				r += 1
				psum += unit
			psum += diff
			if psum > self.max:
				self.max = psum
		return self.max


class Solution:

	def maxSatisfaction(self, satisfaction: List[int]) -> int:
		satisfaction.sort()
		(positive_sum, positive_step, positive_count) = (0, 0, 0)
		for i in satisfaction:
			if i < 0:
				continue
			positive_count += 1
			positive_sum += positive_count * i
			positive_step += i
		negative_count = len(satisfaction) - positive_count
		result = [positive_sum]
		for i in range(negative_count):
			negative_sum = 0
			for j in range(i + 1):
				negative_sum += satisfaction[negative_count - j - 1] * (i - j + 1)
			result.append(negative_sum + positive_sum + positive_step * (i + 1))
		return max(result)


class Solution:

	def maxSatisfaction(self, satisfaction: List[int]) -> int:
		satisfaction.sort(reverse=True)
		s = 0
		res = 0
		for a in satisfaction:
			s += a
			if s <= 0:
				break
			res += s
		return res


class Solution:

	def maxSatisfaction(self, satisfaction: List[int]) -> int:
		satisfaction.sort()
		if satisfaction[0] >= 0:
			return calc_satisfaction(satisfaction)
		min_val = -sys.maxsize
		min_index = None
		for (i, v) in enumerate(satisfaction):
			if 0 > v > min_val:
				min_index = i
				min_val = v
		curr_sum = sum(satisfaction[min_index + 1:])
		while min_index >= 0:
			print((min_index, satisfaction))
			print((satisfaction[min_index], curr_sum))
			if abs(satisfaction[min_index]) < curr_sum:
				curr_sum = curr_sum + satisfaction[min_index]
			else:
				break
			min_index -= 1
		print((min_index, satisfaction))
		return calc_satisfaction(satisfaction[min_index + 1:])

def calc_satisfaction(dishes):
	total = 0
	for (i, s) in enumerate(dishes):
		total += (i + 1) * s
	return total


class Solution:

	def maxSatisfaction(self, satisfaction: List[int]) -> int:
		satisfaction.sort()
		best = 0
		total = 0
		for i in range(len(satisfaction) - 1, -1, -1):
			for j in range(len(satisfaction) - 1, i - 1, -1):
				total += satisfaction[j]
			best = max(best, total)
		return best


from numpy import dot

def coefficient(arr):
	if len(arr) <= 0:
		return 0
	return dot(arr, list(range(1, len(arr) + 1)))

class Solution:

	def maxSatisfaction(self, satisfaction: List[int]) -> int:
		satisfaction.sort()
		runningSum = 0
		for i in reversed(list(range(len(satisfaction)))):
			runningSum += satisfaction[i]
			if runningSum <= 0:
				return coefficient(satisfaction[i + 1:])
		return coefficient(satisfaction)


class Solution:

	def maxSatisfaction(self, satisfaction: List[int]) -> int:
		if max(satisfaction) <= 0:
			return 0
		satisfaction.sort()
		if satisfaction[0] > 0:
			output = 0
			for (i, v) in enumerate(satisfaction):
				output += (i + 1) * v
			return output
		min_val = min((i for i in satisfaction if i >= 0))
		min_index = satisfaction.index(min_val)
		temp_satisfaction = satisfaction[min_index:]
		prev = -1
		current_sum = 0
		while current_sum > prev and len(temp_satisfaction) <= len(satisfaction):
			prev = current_sum
			current_sum = 0
			for (i, v) in enumerate(temp_satisfaction):
				current_sum += (i + 1) * v
			min_index -= 1
			temp_satisfaction.insert(0, satisfaction[min_index])
		return prev if prev > current_sum else current_sum


class Solution:

	def maxSatisfaction(self, satisfaction: List[int]) -> int:
		satisfaction.sort()
		if satisfaction[0] >= 0:
			return calc_satisfaction(satisfaction)
		min_val = -sys.maxsize
		min_index = None
		for (i, v) in enumerate(satisfaction):
			if 0 > v > min_val:
				min_index = i
				min_val = v
		curr_satisfaction = calc_satisfaction(satisfaction[min_index + 1:])
		while True:
			min_index -= 1
			temp_satisfaction = calc_satisfaction(satisfaction[min_index + 1:])
			if temp_satisfaction > curr_satisfaction:
				curr_satisfaction = temp_satisfaction
			else:
				break
		return curr_satisfaction

def calc_satisfaction(dishes):
	total = 0
	for (i, s) in enumerate(dishes):
		total += (i + 1) * s
	return total


class Solution:

	def maxSatisfaction(self, satisfaction: List[int]) -> int:
		satisfaction.sort()
		if satisfaction[0] >= 0:
			return calc_satisfaction(satisfaction)
		min_val = max((s for s in satisfaction if s < 0))
		min_index = satisfaction.index(min_val)
		curr_satisfaction = calc_satisfaction(satisfaction[min_index + 1:])
		while True:
			min_index -= 1
			temp_satisfaction = calc_satisfaction(satisfaction[min_index + 1:])
			if temp_satisfaction > curr_satisfaction:
				curr_satisfaction = temp_satisfaction
			else:
				break
		return curr_satisfaction

def calc_satisfaction(dishes):
	total = 0
	for (i, s) in enumerate(dishes):
		total += (i + 1) * s
	return total


class Solution:

	def maxSatisfaction(self, satisfaction: List[int]) -> int:
		satisfaction.sort()
		total = 0
		beneficial = deque()
		negative = []
		if satisfaction[0] > 0:
			return calc_satisfaction(satisfaction)
		for s in satisfaction:
			if s >= 0:
				beneficial.append(s)
			else:
				negative.append(s)
		curr_satisfaction = calc_satisfaction(beneficial)
		for s in reversed(negative):
			beneficial.appendleft(s)
			temp_satisfaction = calc_satisfaction(beneficial)
			if temp_satisfaction > curr_satisfaction:
				curr_satisfaction = temp_satisfaction
			else:
				beneficial.popleft()
				break
		return curr_satisfaction

def calc_satisfaction(dishes):
	total = 0
	for (i, s) in enumerate(dishes):
		total += (i + 1) * s
	return total


from collections import deque

class Solution:

	def ComputeLikeTime(self, prepared_dishes):
		like_time = 0
		dish_index = 1
		for satisfaction in prepared_dishes:
			like_time += dish_index * satisfaction
			dish_index += 1
		return like_time

	def maxSatisfaction(self, satisfaction):
		satisfaction = sorted(satisfaction, reverse=True)
		prepared_dishes = deque()
		max_satisfaction = 0
		for val in satisfaction:
			prepared_dishes.appendleft(val)
			satisfaction = self.ComputeLikeTime(prepared_dishes)
			if satisfaction > max_satisfaction:
				max_satisfaction = satisfaction
		return max_satisfaction


class Solution:

	def maxSatisfaction(self, satisfaction: List[int]) -> int:
		sat_sort = sorted(satisfaction)
		max_sat = 0
		for i in range(len(sat_sort)):
			sat = sum((t * s for (t, s) in enumerate(sat_sort[i:], start=1)))
			max_sat = max(max_sat, sat, 0)
		return max_sat


class Solution:

	def maxSatisfaction(self, satisfaction: List[int]) -> int:
		sorted_satis = sorted(satisfaction)
		max_satis = sorted_satis[-1]
		if max_satis <= 0:
			return 0

		def calculate_satisfaction(start_index):
			s = 0
			for i in range(len(sorted_satis) - start_index):
				s += (i + 1) * sorted_satis[start_index + i]
			return s
		max_satisfaction = -1
		for i in range(len(sorted_satis)):
			max_satisfaction = max(max_satisfaction, calculate_satisfaction(i))
			if sorted_satis[i] >= 0:
				return max_satisfaction
		return max_satisfaction


class Solution:

	def maxSatisfaction(self, satisfaction: List[int]) -> int:
		satisfaction.sort()
		max_satisfaction = 0
		for i in range(0, len(satisfaction)):
			curr_satisfaction = 0
			timestamp = 1
			for j in range(i, len(satisfaction)):
				curr_satisfaction += satisfaction[j] * timestamp
				timestamp += 1
			max_satisfaction = max(max_satisfaction, curr_satisfaction)
		return max_satisfaction


class Solution:

	def maxSatisfaction(self, satisfaction: List[int]) -> int:
		satisfaction.sort(reverse=True)
		ans = cur_sum = 0
		for ele in satisfaction:
			cur_sum += ele
			if cur_sum >= 0:
				ans += cur_sum
		return ans


class Solution:

	def maxSatisfaction(self, satisfaction: List[int]) -> int:
		satisfaction.sort()
		output = 0
		result = 0
		for i in range(len(satisfaction)):
			output += satisfaction[i] * i
		for i in range(0, len(satisfaction)):
			for j in range(i, len(satisfaction)):
				result += satisfaction[j] * (j - i + 1)
			if output < result:
				output = result
			result = 0
		if output < 0:
			output = 0
		return output


class Solution:

	def maxSatisfaction(self, satisfaction: List[int]) -> int:
		s = sorted(satisfaction, reverse=True)
		total = 0
		i = 0
		while i < len(satisfaction):
			total = max(sum([x * (i + 1) for (i, x) in enumerate(s[0:i + 1][::-1])]), total)
			i += 1
		return total


class Solution:

	def maxSatisfaction(self, satisfaction: List[int]) -> int:
		satisfaction.sort()
		dishes = len(satisfaction)
		best = 0
		for i in range(dishes):
			sum = 0
			tmp = satisfaction[-i - 1:dishes]
			for (j, val) in enumerate(tmp):
				sum += (j + 1) * val
			best = max(best, sum)
		return best


class Solution:

	def mergeSort(self, lst: List[int]) -> int:
		n = len(lst)
		if n <= 1:
			return lst
		mid = n // 2
		L = lst[:mid]
		R = lst[mid:]
		self.mergeSort(L)
		self.mergeSort(R)
		(i, j, k) = (0, 0, 0)
		while i < len(L) and j < len(R):
			if L[i] < R[j]:
				lst[k] = L[i]
				i += 1
			else:
				lst[k] = R[j]
				j += 1
			k += 1
		while i < len(L):
			lst[k] = L[i]
			i += 1
			k += 1
		while j < len(R):
			lst[k] = R[j]
			j += 1
			k += 1
		return lst

	def maxSatisfaction(self, satisfaction: List[int]) -> int:
		n = len(satisfaction)
		possible_sums = [None for i in range(n)]
		print('.......')
		self.mergeSort(satisfaction)
		print(satisfaction)
		for i in range(n):
			arr = satisfaction[i:]
			like_times = [(j + 1) * arr[j] for j in range(len(arr))]
			possible_sums[i] = sum(like_times)
		return max(max(possible_sums), 0)


class Solution:

	def maxSatisfaction(self, satisfaction: List[int]) -> int:
		score = 0
		satisfaction.sort()
		print(satisfaction)
		if satisfaction[0] >= 0:
			for i in range(len(satisfaction)):
				score += (i + 1) * satisfaction[i]
			return score
		elif satisfaction[len(satisfaction) - 1] <= 0:
			return score
		else:
			for i in range(len(satisfaction)):
				score += (i + 1) * satisfaction[i]
			badDishes = []
			for sat in satisfaction:
				if sat < 0:
					badDishes.append(sat)
			for bad in badDishes:
				satisfaction.remove(bad)
				print(satisfaction)
				temp_best = 0
				for i in range(len(satisfaction)):
					temp_best += (i + 1) * satisfaction[i]
				print(temp_best)
				if temp_best > score:
					score = temp_best
			return score


class Solution:

	def maxSatisfaction(self, satisfaction: List[int]) -> int:
		temp = [0] * len(satisfaction)
		output = 0
		satisfaction.sort()
		for (i, _) in enumerate(satisfaction):
			for (j, s) in enumerate(satisfaction[i:]):
				temp[i] += s * (j + 1)
		for s in temp:
			if s > output:
				output = s
		return output


class Solution:

	def maxSatisfaction(self, sat: List[int]) -> int:
		sat = sorted(sat)
		out = [0]
		while len(sat) > 0:
			value = 0
			for (i, v) in enumerate(sat):
				value += v * (i + 1)
			out.append(value)
			print(sat)
			if sat[0] > 0:
				break
			sat = sat[1:]
		return max(out)


class Solution:

	def maxSatisfaction(self, satisfaction: List[int]) -> int:
		satisfaction.sort()
		bestSat = float('-inf')
		for i in range(len(satisfaction)):
			n = len(satisfaction) - 1
			numItems = i + 1
			numAdded = 0
			currSat = 0
			while numAdded <= numItems:
				currSat += satisfaction[n - numAdded] * (numItems - numAdded)
				numAdded += 1
			bestSat = max(bestSat, currSat)
		return max(bestSat, 0)


class Solution:

	def maxSatisfaction(self, satisfaction: List[int]) -> int:
		highScore = 0
		satisfaction.sort(reverse=True)
		for n in range(len(satisfaction)):
			sortedSatisfaction = satisfaction[:len(satisfaction) - n]
			sumSatisfaction = 0
			for i in range(len(sortedSatisfaction)):
				multiplier = len(sortedSatisfaction) - i
				sumSatisfaction += sortedSatisfaction[i] * multiplier
			if sumSatisfaction > highScore:
				highScore = sumSatisfaction
		return highScore


class Solution:

	def maxSatisfaction(self, satisfaction: List[int]) -> int:
		satisfaction.sort(reverse=True)
		(length, res) = (len(satisfaction), 0)
		l = [0] * length
		for i in range(length):
			summ = 0
			for j in range(i + 1):
				l[j] += satisfaction[j]
				summ += l[j]
			if summ > res:
				res = summ
		return res


class Solution:

	def maxSatisfaction(self, satisfaction: List[int]) -> int:
		satisfaction.sort()
		total = 0
		beneficial = [s for s in satisfaction if s >= 0]
		negative = [s for s in satisfaction if s < 0]
		for s in reversed(negative):
			if calc_satisfaction([s] + beneficial) > calc_satisfaction(beneficial):
				beneficial.insert(0, s)
		return calc_satisfaction(beneficial)

def calc_satisfaction(dishes):
	total = 0
	for (i, s) in enumerate(dishes):
		total += (i + 1) * s
	return total


class Solution:

	def maxSatisfaction(self, sat: List[int]) -> int:
		if max(sat) < 0:
			return 0
		arr = []
		sat.sort(reverse=True)
		for i in range(len(sat)):
			sun = 0
			for j in range(len(sat) - i):
				sun += sat[j] * (len(sat) - i - j)
			arr.append(sun)
		print(arr)
		return max(arr)


def merge(arr1, arr2):
	(index1, index2) = (0, 0)
	res = []
	while index1 < len(arr1) or index2 < len(arr2):
		if index1 >= len(arr1) or (index2 < len(arr2) and arr1[index1] > arr2[index2]):
			res.append(arr2[index2])
			index2 += 1
		else:
			res.append(arr1[index1])
			index1 += 1
	return res

def mergeSort(arr):
	if len(arr) <= 1:
		return arr
	m = int(len(arr) / 2)
	return merge(mergeSort(arr[:m]), mergeSort(arr[m:]))

def splitAtZero(sortedArr):
	for i in range(len(sortedArr)):
		if sortedArr[i] >= 0:
			return (sortedArr[:i], sortedArr[i:])
	return (sortedArr, [])

def coefficient(arr):
	res = 0
	for i in range(len(arr)):
		res += (i + 1) * arr[i]
	return res

class Solution:

	def maxSatisfaction(self, unsortedSatisfaction: List[int]) -> int:
		satisfaction = mergeSort(unsortedSatisfaction)
		(negative, nonnegative) = splitAtZero(satisfaction)
		res = nonnegative[:]
		for dish in reversed(negative):
			attempt = [dish] + res[:]
			if coefficient(attempt) > coefficient(res):
				res = attempt[:]
			else:
				return coefficient(res)
		return coefficient(res)


class Solution:

	def maxSatisfaction(self, satisfaction: List[int]) -> int:
		satisfaction.sort()
		if satisfaction[-1] <= 0:
			return 0
		last_sum = 0
		temp = [0] * len(satisfaction)
		for i in range(len(satisfaction), 0, -1):
			temp = [a + b for (a, b) in zip(temp, [0] * (i - 1) + satisfaction[i - 1:])]
			score = sum(temp)
			if last_sum > score:
				break
			last_sum = score
		return last_sum


class Solution:

	def maxSatisfaction(self, satisfaction: List[int]) -> int:
		satisfaction.sort()
		dp = [[0] * len(satisfaction) for i in range(len(satisfaction))]
		maxVal = 0
		for i in range(len(satisfaction)):
			count = 1
			tempM = 0
			for j in range(i, len(satisfaction)):
				dp[i][j] = satisfaction[j] * count
				tempM += dp[i][j]
				count += 1
			maxVal = max(maxVal, tempM)
		return maxVal


class Solution:

	def maxSatisfaction(self, satisfaction: List[int]) -> int:
		sortlist = sorted(satisfaction, reverse=True)
		a = 0
		b = 0
		for i in range(len(sortlist)):
			a += sortlist[i]
			if a <= 0:
				break
			else:
				b += 1
		return sum((sortlist[j] * (b - j) for j in range(0, b)))


class Solution:

	def maxSatisfaction(self, satisfaction: List[int]) -> int:
		satisfaction.sort()
		m = 0
		while len(satisfaction) > 0:
			s = sum((satisfaction[i] * (i + 1) for i in range(len(satisfaction))))
			m = max(s, m)
			satisfaction = satisfaction[1:]
		return m


import numpy as np

class Solution:

	def maxSatisfaction(self, satisfaction: List[int]) -> int:
		output = []
		length = len(satisfaction)
		satisfaction_srt = sorted(satisfaction)
		for i in range(length):
			satisfaction = satisfaction_srt[i:]
			time = list(range(1, length + 1 - i))
			output.append(np.dot(time, satisfaction))
		if max(output) < 0:
			return 0
		else:
			return max(output)
ans = Solution()
ans.maxSatisfaction([-1, -8, 0, 5, -7])


class Solution:

	def maxSatisfaction(self, satisfaction: List[int]) -> int:
		satisfaction = sorted(satisfaction)
		ans = 0
		for (i, s) in enumerate(satisfaction):
			index = i
			curr_ans = 0
			j = 1
			while index <= len(satisfaction) - 1:
				curr_ans += j * satisfaction[index]
				j += 1
				index += 1
			ans = max(ans, curr_ans)
		return ans


class Solution:

	def maxSatisfaction(self, satisfaction) -> int:
		n = satisfaction.__len__()
		if n == 0:
			return 0
		satisfaction.sort()
		if satisfaction[-1] <= 0:
			return 0
		else:
			mannux = 0
			while satisfaction:
				tem = 0
				for i in range(n):
					tem += (i + 1) * satisfaction[i]
				if mannux < tem:
					mannux = tem
				satisfaction.pop(0)
				n -= 1
			return mannux


class Solution:

	def maxSatisfaction(self, s: List[int]) -> int:
		s.sort(reverse=True)
		maxi = 0
		for i in range(len(s)):
			t = 0
			for j in range(i + 1):
				t += s[j] * (i + 1 - j)
			maxi = max(maxi, t)
		return maxi


class Solution:

	def maxSatisfaction(self, satisfaction: List[int]) -> int:
		n = len(satisfaction)
		satisfaction.sort()
		ans = 0
		for i in range(n):
			coef = 0
			for k in range(1, n + 1):
				if i + k - 1 < n:
					coef += satisfaction[i + k - 1] * k
			ans = max(ans, coef)
		return ans


class Solution:

	def maxSatisfaction(self, satisfaction: List[int]) -> int:
		satisfaction.sort()
		sums = []
		temp = [0] * len(satisfaction)
		for i in range(len(satisfaction), 0, -1):
			temp = [a + b for (a, b) in zip(temp, [0] * (i - 1) + satisfaction[i - 1:])]
			sums.append(sum(temp))
		result = max(sums)
		return result if result > 0 else 0


class Solution:

	def maxSatisfaction(self, satisfaction: List[int]) -> int:
		ordered_satis = sorted(satisfaction)
		nums = len_num = len(ordered_satis)
		max_satis = 0
		while len_num > 0:
			tem_max = 0
			for (i, j) in enumerate(ordered_satis):
				if nums - len_num > i:
					continue
				tem_max += (i + 1 + len_num - nums) * j
			max_satis = max(max_satis, tem_max)
			len_num -= 1
		return max_satis


class Solution:

	def maxSatisfaction(self, satisfaction: List[int]) -> int:
		satisfaction.sort(reverse=True)
		max_satisfaction = 0
		satis = 0
		sum_ = 0
		for s in satisfaction:
			satis += sum_ + s
			sum_ += s
			max_satisfaction = max(max_satisfaction, satis)
			if sum_ < 0:
				break
		return max_satisfaction


class Solution:

	def maxSatisfaction(self, satisfaction: List[int]) -> int:
		satisfaction.sort()
		table = [[None] * len(satisfaction) for i in range(len(satisfaction))]
		for i in range(len(satisfaction)):
			for j in range(i, len(satisfaction)):
				table[i][j] = satisfaction[j] * (i + 1)
		bestSat = float('-inf')
		for i in range(len(satisfaction)):
			row = i
			col = len(satisfaction) - 1
			currSat = 0
			while row >= 0:
				currSat += table[row][col]
				row -= 1
				col -= 1
			bestSat = max(bestSat, currSat)
		return max(bestSat, 0)


class Solution:

	def maxSatisfaction(self, satisfaction: List[int]) -> int:
		satisfaction.sort()
		n = len(satisfaction)
		dp = [-1000000009] * (n + 1)
		dp[0] = 0
		for i in range(n):
			for j in range(i, -1, -1):
				dp[j + 1] = max(dp[j + 1], satisfaction[i] * (j + 1) + dp[j])
		answer = -1000000009
		for i in range(n + 1):
			answer = max(dp[i], answer)
		return answer


class Solution:

	def maxSatisfaction(self, satisfaction: List[int]) -> int:
		currmax = 0
		satsort = sorted(satisfaction)
		leng1 = len(satsort)
		for nn in range(leng1):
			satpart = satsort[nn:]
			leng2 = leng1 - nn
			time = [ii for ii in range(1, leng2 + 1)]
			coeff = []
			for ii in range(leng2):
				coeff.append(satpart[ii] * time[ii])
			cumul = [coeff[0]]
			for ii in range(1, leng2):
				cumul.append(cumul[ii - 1] + coeff[ii])
			for elem in cumul:
				if currmax < elem:
					currmax = elem
		return currmax


class Solution:

	def maxSatisfaction(self, s: List[int]) -> int:
		s.sort()
		l = len(s)
		dp = [[0 for _ in range(l)] for _ in range(l)]
		for i in range(l):
			for j in range(l):
				if j <= i:
					if j == 0:
						dp[i][j] = (j + 1) * s[i]
					else:
						dp[i][j] = dp[i - 1][j - 1] + (j + 1) * s[i]
		print(max(dp[-1]))
		return max(max(dp[-1]), 0)


class Solution:

	def maxSatisfaction(self, satisfaction: List[int]) -> int:
		satisfaction.sort()
		n = len(satisfaction)
		dp = [[-1000000000.0] * n for i in range(n)]
		for i in range(n):
			for j in range(i + 1):
				dp[i][j] = max((dp[i - 1][j - 1] if i - 1 >= 0 and j - 1 >= 0 else 0) + satisfaction[i] * (j + 1), dp[i - 1][j])
		ret = max(dp[-1])
		return ret if ret > 0 else 0


import numpy as np

class Solution:

	def maxSatisfaction(self, satisfaction: List[int]) -> int:
		satisfaction.sort()
		sums = []
		temp = [0] * len(satisfaction)
		for i in range(len(satisfaction), 0, -1):
			temp = np.add(temp, [0] * (i - 1) + satisfaction[i - 1:])
			sums.append(np.sum(temp))
		result = max(sums)
		return result if result > 0 else 0


class Solution:

	def maxSatisfaction(self, satisfaction: List[int]) -> int:
		sat = sorted(satisfaction)
		dp = [[-float('inf')] * (len(sat) + 1) for i in range(len(sat) + 1)]
		for i in range(len(sat) + 1):
			dp[0][i] = 0
		ans = 0
		for i in range(1, len(sat) + 1):
			for j in range(i, len(sat) + 1):
				dp[i][j] = max(dp[i][j], dp[i - 1][j - 1] + sat[j - 1] * i)
				ans = max(ans, dp[i][j])
		return ans


class Solution:

	def maxSatisfaction(self, satisfaction: List[int]) -> int:
		satisfaction.sort()
		totalDishes = len(satisfaction)
		dp = {}

		def cookOne(i0, n0):
			if i0 == totalDishes:
				return 0
			if (i0, n0) in dp:
				return dp[i0, n0]
			if satisfaction[i0] >= 0:
				dp[i0, n0] = (n0 + 1) * satisfaction[i0] + cookOne(i0 + 1, n0 + 1)
			else:
				dp[i0, n0] = max((n0 + 1) * satisfaction[i0] + cookOne(i0 + 1, n0 + 1), cookOne(i0 + 1, n0))
			return dp[i0, n0]
		return cookOne(0, 0)


class Solution:

	def maxSatisfaction(self, satisfaction: List[int]) -> int:
		res = total = 0
		i = len(satisfaction) - 1
		satisfaction.sort()
		while i >= 0 and satisfaction[i] + total > 0:
			total += satisfaction[i]
			res += total
			i -= 1
		return res


class Solution:

	def maxSatisfaction(self, s: List[int]) -> int:
		s.sort()
		n = len(s)
		dp = [0] * (n + 2)
		for dish in range(n - 1, -1, -1):
			maxT = n + 1
			for time in range(1, maxT):
				if dish == n - 1:
					dp[time] = time * s[dish]
				else:
					include = time * s[dish] + dp[time + 1]
					dp[time] = max(include, dp[time])
			maxT -= 1
		return max(0, dp[1])


class Solution:

	def maxSatisfaction(self, satisfaction: List[int]) -> int:
		satisfaction.sort()

		@lru_cache(None)
		def dp(i, time):
			if i == len(satisfaction):
				return 0
			return max(time * satisfaction[i] + dp(i + 1, time + 1), dp(i + 1, time))
		return dp(0, 1)


class Solution:

	def maxSatisfaction(self, satisfaction: List[int]) -> int:
		satisfaction.sort()
		n = len(satisfaction)
		dp = [[0 for j in range(n + 1)] for i in range(n + 1)]
		for j in range(1, n + 1):
			dp[1][j] = satisfaction[j - 1]
		ans = 0
		for i in range(2, n + 1):
			for j in range(i, n + 1):
				dp[i][j] = dp[i - 1][j - 1] + satisfaction[j - 1] * i
				ans = max(ans, dp[i][j])
		return ans


class Solution:

	def maxSatisfaction(self, satisfaction: List[int]) -> int:
		satisfaction.sort()
		n = len(satisfaction)
		import functools

		@functools.lru_cache(None)
		def DP(i, j):
			if i == n:
				return 0
			return max(satisfaction[i] * j + DP(i + 1, j + 1), DP(i + 1, j))
		return DP(0, 1)