Maximize Sum of Array
Updated
Problem statement
You are given an array of integers arr. Repeat these steps until the array is empty:
- Choose one element of the current array that you have not chosen before.
- Add it to your total sum. The chosen element stays in the array.
- Remove the first and the last element of the array. If only one element is left, remove it.
Each element can be chosen at most once, and you must choose an element in every round. So plan your choices so that every round still has an element you have not chosen.
For example, with [1, 9, 2] there are two rounds. The second round only has [9], so save 9 for it and choose 2 in the first round. The total is 2 + 9 = 11.
Return the largest total sum you can get.
Function
maximizeSum(arr: int[]) → int
Complete the function maximizeSum in the editor.
maximizeSum has the following parameter:
int arr[n]: the starting array
Returns
int: the largest total sum
Examples
Example 1
arr = [4, 4, 8, 5, 3, 2]return = 17There are three rounds. Round 1: choose 5 from [4, 4, 8, 5, 3, 2], then remove 4 and 2. The total is 5. Round 2: choose 4 from [4, 8, 5, 3], then remove 4 and 3. The total is 5 + 4 = 9. Round 3: choose 8 from [8, 5], then remove 8 and 5. The total is 9 + 8 = 17. Three rounds choose three different elements, and the three largest values are 8, 5 and 4, so no plan beats 8 + 5 + 4 = 17. The answer is 17.
Constraints
1 <= n <= 10^5, wherenis the length ofarr1 <= arr[i] <= 10^4
More Amazon interview questions
- LRU Cache for Query ResultsPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Maximal SquareONSITE INTERVIEW · Seen Nov 2026
- Serialize and Deserialize a Binary TreeONSITE INTERVIEW · Seen Nov 2026
- Course SchedulePHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Course Schedule IIPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Diagonal Traversal of a Binary TreeONSITE INTERVIEW · Seen Nov 2026
- Minimum Time to Spread Through a GridPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Consistent-Hash Packet RouterPHONE SCREEN · Seen Nov 2026
- Count Connected ComponentsPHONE SCREEN · Seen Nov 2026
- Maximize K-Element AND with an Increment BudgetOA · Seen Nov 2026
Similar questions at other companies
- Minimum Cost K-Capable ModelsMicrosoft · OAMicrosoft interview questions
- Optimal TransferSnowflake · OASnowflake interview questions
- Gas Station Loop StartNutanix · OANutanix interview questions
- Redistribute MegaseedsRubrik · OARubrik interview questions
- Maximum Distinct Items Within a BudgetAdobe · OAAdobe interview questions
- Minimum AmountBelvedere Trading · OA
- Focus on Efficiency (2024 NG)Google · OAGoogle interview questions
- Running Through Walls with Limited EnergyScale AI · OAScale AI interview questions
- Make the Array PositiveAtlassian · OAAtlassian interview questions
- Maximize Compatible Car RidersUber Freight · PHONE SCREEN · ONSITE INTERVIEWUber Freight interview questions