Maximum Value of the Last Robot
Updated
Problem statement
There are n robots standing in a row. Robot i (counting from the left, starting at 0) holds the integer values[i].
While more than one robot is left, choose any robot and let it remove one of its neighbours. A robot's neighbours are the closest robot still standing on its left and the closest robot still standing on its right, if they exist.
When a robot with value x removes a robot with value y, the removed robot leaves the row and the remover's value becomes x - y. The robots keep their order.
The process stops when exactly one robot is left. Return the largest value that this last robot can have.
Function
maxLastRobotValue(values: int[]) → longExamples
Example 1
values = [2,1,2,1]return = 4- Robot 1 (value
1) removes robot 2 (value2) and becomes1 - 2 = -1. The row is[2, -1, 1]. - The same robot (value
-1) removes its right neighbour (value1) and becomes-1 - 1 = -2. The row is[2, -2]. - Robot 0 removes the last other robot and becomes
2 - (-2) = 4.
No order of removals ends higher than 4.
Example 2
values = [1,-2,3]return = 6- Robot 1 (value
-2) removes robot 2 (value3) and becomes-2 - 3 = -5. The row is[1, -5]. - Robot 0 removes it and becomes
1 - (-5) = 6.
The answer 6 equals 1 + 2 + 3, the sum of the absolute values, and no robot can end higher than that.
Example 3
values = [-3,-5,-1]return = 7- Robot 2 (value
-1) removes robot 1 (value-5) and becomes-1 - (-5) = 4. The row is[-3, 4]. - That robot (value
4) removes robot 0 and becomes4 - (-3) = 7.
The sum of the absolute values is 9, but here every value is negative and one of them must still count against the total. Giving up the one closest to zero, -1, costs the least: 3 + 5 - 1 = 7.
Constraints
1 <= values.length <= 10^5-10^9 <= values[i] <= 10^9
More Nutanix Online Assessment questions
- Good SubsequencesOA · Seen Jul 2026
- Min Cost to Connect All PointsOA · Seen Jun 2026
- Digit Changes for a Multiple of 9OA · Seen Aug 2025
- Gas Station Loop StartOA · Seen Aug 2025
- Number of Players (for MTS2)OA · Seen Oct 2024
- Work Schedules (for MTS2)OA · Seen Oct 2024
- Minimum Operations to Convert ArrayOA · Seen Apr 2024
- No Adjacent CharactersOA · Seen Apr 2024
- Build a BST From a ListOA · Seen Nov 2022
- Delete Even-Valued Nodes From a Linked ListOA · Seen Nov 2022
Similar questions at other companies
- Minimum Rounds to Complete All TasksInfosys · OAInfosys interview questions
- Minimize Adjacent Squared-Difference Cost with One InsertionMcKinsey & Company · OAMcKinsey & Company interview questions
- Maximize Revenue from Decreasing InventoryChubb · OAChubb interview questions
- Minimum Values with Even Powers of TwoVisa · OAVisa interview questions
- Minimize Adjacent Squared-Difference Cost with One InsertionMicrosoft · OAMicrosoft interview questions
- Minimum Halvings for Alternating ParityIBM · OAIBM interview questions
- Resource AllocationMaven Securities · OAMaven Securities interview questions
- Rock JumpingIMC Trading · OAIMC Trading interview questions
- Minimum Total Batch ExpenseAmazon · OA
- Minimum Increments for Stepwise TowersZipRecruiter · OAZipRecruiter interview questions