Amazon Academy has launched a new course on Quantum Physics. The course has n chapters,…
- User
Amazon Academy has launched a new course on Quantum Physics.
The course has n chapters, each chapter has memory[i] memory points, which a student gains or loses while reading that chapter. The course has a requirement: in order to study the ith chapter, the student must revisit all the previous chapters. A student gains memory[0] + memory[1] + ... + memory[i] memory points for reading the ith chapter. The total memory points is the sum of memory points gained while reading each chapter.
Students can read the chapters in any order, and want to maximize their total memory points. Find the maximum total memory points a student can score ensuring that all the chapters are read.
Example
memory [3, 4, 5]
Considering all permutations of reading the chapters and their total memory points:
[3, 4, 5] Corresponding memory points will be [3, 7, 12], thus total memory points will be 3 +7+12=21
[3, 5, 4] Corresponding memory points will be [3, 8, 12], thus total memory points will be 3 +8+12-23
[4, 3, 5] - Corresponding memory points will be [4, 7, 12), thus total memory points will be 4 +7+12-23
[4, 5, 3] Corresponding memory points will be [4, 9, 12], thus total memory points will be 4
+9+12-25
• [5. 3, 4] - Corresponding memory points will be [5, 8, 12], thus total memory points will be 5 +8+12-25
[5, 4, 3] Corresponding memory points will be [5, 9, 12], thus total memory points will be 5 +9+12-26
The maximum number of total memory points is 26.
Function Description
Complete the function maximize TotalMemoryPoints in the editor below.
maximize TotalMemoryPoints has the following parameter: int memory[n]: the memory points associated with each chapter
Returns
long, int the maximum possible total memory points
Constraints
1 ≤ n ≤ 105
⚫-10^3 s memory[i] ≤ 10^3
► Input Format For Custom Testing
Sample Case 0
Sample Input For Custom Testing
STDIN
FUNCTION
3 memory[] size, n = 3
1
memory [1, -2, 3]
-2
3
Sample Output
9
Explanation
The permutation with maximum total memory points is [3, 1, -2]. The corresponding memory points for each chapter are [3, 4, 2] resulting in the maximum sum of 3 +4+2=
Sample Case 1
Sample Input For Custom Testing
STDIN
FUNCTION
memory[] size n = 4
memory [2, 2, 2, 2]
4
2
2
2
2
Sample Output
20
Explanation
The total memory points will remain the same regardless of order. The corresponding memory points are [2, 4, 6, 8], resulting in the maximum total of 2+4+6+8-20.
- Assistant
To solve this problem, the goal is to determine the optimal order in which a student should read the chapters to maximize the total memory points. Here's a step-by-step explanation of the approach:
Understanding the Problem
-
Memory Points Calculation:
- When a student reads a chapter (i), they gain (or lose) memory points equal to the sum of all memory points of the chapters read up to and including chapter (i).
- Therefore, if a student reads chapters in the order ([c_1, c_2, \dots, c_n]), the total memory points would be: [ \text{Total Memory} = c_1 + (c_1 + c_2) + (c_1 + c_2 + c_3) + \dots + (c_1 + c_2 + \dots + c_n) ] Simplifying this, it becomes: [ \text{Total Memory} = c_1 \times n + c_2 \times (n-1) + \dots + c_n \times 1 ]
- This shows that the earlier a chapter is read, the more weight its memory points contribute to the total.
-
Optimal Ordering:
- To maximize the total memory points, chapters with higher memory points should be read earlier.
- Conversely, chapters with negative memory points should be read as late as possible to minimize their negative impact.
Algorithm Steps
-
Sort the Chapters:
- Sort the
memoryarray in descending order. This ensures that chapters with the highest memory points are read first.
- Sort the
-
Calculate the Total Memory Points:
- Initialize a variable
totalto store the cumulative memory points. - Iterate through the sorted
memoryarray. - For each chapter at index
i(0-based), multiply its memory points by ((n - i)) and add the result tototal. - This accounts for the weight each chapter's memory points contribute based on their reading order.
- Initialize a variable
-
Return the Result:
- After processing all chapters,
totalwill hold the maximum possible total memory points.
- After processing all chapters,
Implementation
Here's how you can implement the above approach in Python:
def maximizeTotalMemoryPoints(memory): # Sort the memory array in descending order memory_sorted = sorted(memory, reverse=True) n = len(memory_sorted) total = 0 # Calculate total memory points for i in range(n): total += memory_sorted[i] * (n - i) return totalExamples
Let's verify the algorithm with the provided samples:
-
Sample Case 0:
- Input:
memory = [1, -2, 3] - Sorted:
[3, 1, -2] - Calculation: [ 3 \times 3 + 1 \times 2 + (-2) \times 1 = 9 + 2 - 2 = 9 ]
- Output:
9
- Input:
-
Sample Case 1:
- Input:
memory = [2, 2, 2, 2] - Sorted:
[2, 2, 2, 2](No change as all elements are equal) - Calculation: [ 2 \times 4 + 2 \times 3 + 2 \times 2 + 2 \times 1 = 8 + 6 + 4 + 2 = 20 ]
- Output:
20
- Input:
Conclusion
By sorting the chapters in descending order based on their memory points and calculating the cumulative weighted sum, we ensure that chapters contributing positively are maximized early on, while minimizing the impact of any negative contributions. This approach guarantees the maximum possible total memory points.
-