Question

17.16. The Masseuse

中文文档

Description

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

Solutions

Solution 1

class Solution:
  def massage(self, nums: List[int]) -> int:
    f = g = 0
    for x in nums:
      f, g = g + x, max(f, g)
    return max(f, g)

class Solution {
  public int massage(int[] nums) {
    int f = 0, g = 0;
    for (int x : nums) {
      int ff = g + x;
      int gg = Math.max(f, g);
      f = ff;
      g = gg;
    }
    return Math.max(f, g);
  }
}

class Solution {
public:
  int massage(vector<int>& nums) {
    int f = 0, g = 0;
    for (int& x : nums) {
      int ff = g + x;
      int gg = max(f, g);
      f = ff;
      g = gg;
    }
    return max(f, g);
  }
};

func massage(nums []int) int {
  f, g := 0, 0
  for _, x := range nums {
    f, g = g+x, max(f, g)
  }
  return max(f, g)
}

function massage(nums: number[]): number {
  let f = 0,
    g = 0;
  for (const x of nums) {
    const ff = g + x;
    const gg = Math.max(f, g);
    f = ff;
    g = gg;
  }
  return Math.max(f, g);
}