广州网站设计培训,网站开发与维护项目招标,绵阳做网站的公司,wordpress cdn 腾讯云按摩师 1. 题目解析2. 讲解算法原理3. 编写代码 1. 题目解析 题目地址#xff1a;点这里 2. 讲解算法原理 首先#xff0c;给定一个整数数组 nums#xff0c;其中 nums[i] 表示第 i 天的预约时间长度。 定义两个辅助数组 f 和 g#xff0c;长度都为 n#xff08;n 是数组… 按摩师 1. 题目解析2. 讲解算法原理3. 编写代码 1. 题目解析 题目地址点这里 2. 讲解算法原理 首先给定一个整数数组 nums其中 nums[i] 表示第 i 天的预约时间长度。 定义两个辅助数组 f 和 g长度都为 nn 是数组 nums 的长度。 数组 f 表示在第 i 天选择预约时的最大总时长。数组 g 表示在第 i 天选择不预约时的最大总时长。 初始化数组 f 和 g 的第一个元素 f[0] nums[0]表示第一天选择预约总时长为第一天的预约时长。g[0] 0表示第一天选择不预约总时长为0。 从第二天开始从左到右遍历整个数组 nums计算每一天的最大总时长 对于第 i 天如果选择预约则总时长为前一天选择不预约的最大总时长 g[i-1] 加上第 i 天的预约时长 nums[i]即 f[i] g[i-1] nums[i]。对于第 i 天如果选择不预约则总时长为前一天选择预约和不预约的最大总时长中的较大值即 g[i] max(f[i-1], g[i-1])。 最后返回最后一天选择预约和不预约的最大总时长的较大值即 max(f[n-1], g[n-1])其中 n 是数组 nums 的长度。 3. 编写代码
class Solution {
public:int massage(vectorint nums) {int nnums.size();//处理细节if(n0) return 0;vectorint f(n); vectorint g(n); f[0]nums[0],g[0]0;for(int i1;in;i){f[i]g[i-1]nums[i];g[i]max(f[i-1],g[i-1]);} return max(f[n-1],g[n-1]);}
};
