A popular masseuse receives a sequence of back-to-back appointment requests and is debating which ones to accept. She needs a break between appointments and therefore she cannot accept any adjacent requests. Given a sequence of back-to-back appoint ment requests, find the optimal (highest total booked minutes) set the masseuse can honor. Return the number of minutes.
Note: This problem is slightly different from the original one in the book.
Example 1:
Input: [1,2,3,1] Output: 4 Explanation: Accept request 1 and 3, total minutes = 1 + 3 = 4
Example 2:
Input: [2,7,9,3,1] Output: 12 Explanation: Accept request 1, 3 and 5, total minutes = 2 + 9 + 1 = 12
Example 3:
Input: [2,1,4,5,3,1,1,3] Output: 12 Explanation: Accept request 1, 3, 5 and 8, total minutes = 2 + 4 + 3 + 3 = 12
class Solution:
def massage(self, nums: List[int]) -> int:
if not nums:
return 0
n = len(nums)
if n < 2:
return nums[0]
a, b = nums[0], max(nums[0], nums[1])
res = b
for i in range(2, n):
res = max(a + nums[i], b)
a, b = b, res
return resclass Solution {
public int massage(int[] nums) {
if (nums == null) {
return 0;
}
int n = nums.length;
if (n < 2) {
return n == 0 ? 0 : nums[0];
}
int a = nums[0], b = Math.max(nums[0], nums[1]);
int res = b;
for (int i = 2; i < n; ++i) {
res = Math.max(a + nums[i], b);
a = b;
b = res;
}
return res;
}
}