一、问题描述

题目描述

假设知道某段连续时间内股票价格，计算通过买入卖出可获得的最大收益。

输入一个大小为 n 的数 price(p1,p2,p3,p4…….pn),pi 是第i天的股票价格。

pi 的格式为股票价格（非负整型）加上货币单位 Y 或者 S,其中 Y 代表人民币，S 代表美元，这里规定 1 美元可以兑换 7 人民币。

Pi 样例 1：123Y 代表 123 元人民币

pi 样例 2：123S 代表 123 元美元，可兑换 861 人民币。

假设你可以在任何一天买入或者卖出股票，也可以选择放弃交易，请计其在交易周期 n 天内你能获得的最大收（以人民币计算）。

输入描述

输入一个包含交易周期内各天股票价格的字符串，以空格分隔。不考虑输入异常情况。

输出描述

输出一个整型数代表在交易周期 n 天内你能获得的最大收益，n 不能超过 10000。

备注

股票价格只会用 Y 人民币或 S 美元进行输入，不考虑其他情况。

用例

输入

2Y 3S 4S 6Y 8S

输出

76

说明
无

题目解析

本题其实少了一句话，那就是，手上只能保留一只股票，不能保留多只股票。

如果可以保留多只股票，则用例 2Y 3S 4S 6Y 8S，我前四个全要，即有四只股票，然后全部以 8S 价格卖出，那么最大利润为 8S * 4 - (2Y + 3S + 4S + 6Y) = 167，而不是76。

用例中的76输出，前提是手上只能保留一只股票。

即：

• 2Y买进，3S卖出，赚19
• 3S买进，4S卖出，赚7
• 6Y买进，8S卖出，赚50

共转76

这是一种贪心思维，即买涨不买跌，这样就稳赚不赔了。如上折线图，只买上升区段，不买下跌区段。

解题思路

1. 解析输入：

   • 将输入的股票价格字符串按空格分隔，得到每天的股票价格。
   • 将每个股票价格转换为人民币。

2. 计算最大收益：

   • 使用贪心算法，遍历每天的股票价格。
   • 对于每一天，如果当天的价格比前一天高，则卖出前一天的股票并买入当天的股票。
   • 计算每次交易的收益，并累加到总收益中。

3. 输出结果：

   • 遍历完成后，输出总收益。

通过这种方法，我们可以有效地计算出在交易周期内能获得的最大收益。时间复杂度为O(n)，其中n是交易周期的天数，因为我们只需要遍历一次。

二、JavaScript算法源码

以下是 JavaScript 代码的详细中文注释和讲解，帮助您理解每个部分的功能和工作原理。

代码分析

javascript">const readline = require("readline");const rl = readline.createInterface({input: process.stdin,output: process.stdout,
});rl.on("line", (line) => {const arr = line.split(" ").map((price) => {const num = parseInt(price.substring(0, price.length - 1));return price.at(-1) === "Y" ? num : num * 7;});console.log(getResult(arr));
});function getResult(arr) {let ans = 0;for (let i = 1; i < arr.length; i++) {ans += Math.max(0, arr[i] - arr[i - 1]);}return ans;
}

1. 引入 readline 模块

javascript">const readline = require("readline");

• readline 是 Node.js 提供的一个内置模块，用于从控制台（标准输入）逐行读取数据，适合在 ACM 竞赛模式（交互式模式）下使用。
• require("readline") 语句引入该模块。

2. 创建 readline 接口

javascript">const rl = readline.createInterface({input: process.stdin,output: process.stdout,
});

• readline.createInterface 创建一个接口，用于从控制台读取输入和输出。
• input: process.stdin：表示读取标准输入（键盘输入）。
• output: process.stdout：表示向标准输出（控制台）写入数据。

3. 监听输入的每一行数据

javascript">rl.on("line", (line) => {const arr = line.split(" ").map((price) => {const num = parseInt(price.substring(0, price.length - 1));return price.at(-1) === "Y" ? num : num * 7;});console.log(getResult(arr));
});

• rl.on("line", ...) 监听每一行输入数据。当用户输入一行并按下回车时，回调函数会被触发。
• line：输入的每一行文本。

处理输入数据：

javascript">const arr = line.split(" ").map((price) => {const num = parseInt(price.substring(0, price.length - 1));return price.at(-1) === "Y" ? num : num * 7;
});

1. 分割字符串：

   • line.split(" ")：将输入的行按空格拆分成多个字符串。假设输入为 "10Y 5D 7Y", 则 split(" ") 后得到 ["10Y", "5D", "7Y"]。

2. 转换每个价格：

   • map((price) => { ... })：遍历 split(" ") 后得到的数组，对每个价格（如 "10Y"）进行处理。

   3. 去除最后一个字符并转换为数字：

      javascript">const num = parseInt(price.substring(0, price.length - 1));
      

      • 使用 substring(0, price.length - 1) 去除价格字符串的最后一个字符（"Y" 或 "D"）。
      • parseInt() 将剩余的部分转换为整数。例如，"10Y" 转换为 10。

   4. 根据单位判断并处理：

      javascript">return price.at(-1) === "Y" ? num : num * 7;
      

      • 使用 price.at(-1) 获取价格字符串的最后一个字符（即 Y 或 D）。

      • 如果最后一个字符是 "Y"，则直接返回 num。

      • 如果最后一个字符是 "D"，则将 num 乘以 7，转换为以“Y”为单位的金额。例如，"5D" 会变成 5 * 7 = 35。

      • 注意：在此代码中，单位 "Y" 表示年，单位 "D" 表示日，假设题目要求把所有的日转换为年（每年有 365 天）。

调用 getResult 函数并输出结果：

javascript">console.log(getResult(arr));

• 调用 getResult(arr) 函数，传入处理过的价格数组 arr。
• 使用 console.log 打印返回的结果。

4. getResult 函数

javascript">function getResult(arr) {let ans = 0;for (let i = 1; i < arr.length; i++) {ans += Math.max(0, arr[i] - arr[i - 1]);}return ans;
}

功能说明：

• 该函数计算并返回根据价格变动的总和。具体来说，它计算每个价格与前一个价格的差异，但如果差异为负数，则将其视为零。
• arr：已经处理过的价格数组（单位已转换为年，单位是整数）。

代码详解：

1. 初始化 ans：

   javascript">let ans = 0;
   

   • ans 用于累积结果。

2. 遍历价格数组：

   javascript">for (let i = 1; i < arr.length; i++) {ans += Math.max(0, arr[i] - arr[i - 1]);
   }
   

   • 从数组的第二个元素开始（即 i = 1），逐一遍历每个元素。
   • arr[i] - arr[i - 1] 计算当前价格与前一个价格的差值。
   • Math.max(0, ...) 确保如果差值为负数，则不对 ans 产生影响（即差值小于 0 时视为 0）。
   • 如果差值为正，则将其累加到 ans 中。

3. 返回结果：

   javascript">return ans;
   

   • 最终返回 ans，即所有正差值的总和。

总结

1. 输入：

   • 输入一行包含多个价格和单位的字符串，价格单位可能是 Y（年）或 D（日）。

2. 处理：

   • 将每个价格字符串的最后一个字符去掉并转换为数字。
   • 如果单位是 D（日），则将该价格转换为以年为单位的价格（假设每年有 365 天）。

3. 计算：

   • 遍历处理后的价格数组，计算每个价格与前一个价格之间的正差值，累加起来。

4. 输出：

   • 输出所有正差值的总和。

示例

输入：

10Y 5D 7Y

处理过程：

1. 10Y → 10（不变）
2. 5D → 5 * 7 = 35
3. 7Y → 7（不变）

转换后的数组为：[10, 35, 7]。

getResult 函数计算过程：

• 比较 35 - 10 = 25（正差值，累加到 ans）。
• 比较 7 - 35 = -28（负差值，不累加）。
• 返回 ans = 25。

输出：

25

---

如果有其他问题，或需要进一步的解释，随时提问！

三、Java算法源码

以下是 Java 代码的详细中文注释和讲解：

---

代码结构

java">import java.util.Arrays;
import java.util.Scanner;public class Main {// 主方法：程序入口public static void main(String[] args) {Scanner sc = new Scanner(System.in);// 处理输入数据Integer[] arr =Arrays.stream(sc.nextLine().split(" ")).map(p -> {int num = Integer.parseInt(p.substring(0, p.length() - 1));String unit = p.substring(p.length() - 1);return "Y".equals(unit) ? num : num * 7;}).toArray(Integer[]::new);// 调用算法并输出结果System.out.println(getResult(arr));}// 算法入口：计算价格变动的总和public static int getResult(Integer[] arr) {int ans = 0;for (int i = 1; i < arr.length; i++) {ans += Math.max(0, arr[i] - arr[i - 1]);}return ans;}
}

---

详细注释和讲解

1. 导入必要的类

java">import java.util.Arrays;
import java.util.Scanner;

• java.util.Arrays：提供数组操作的工具类，例如将流转换为数组。
• java.util.Scanner：用于从控制台读取用户输入。

---

2. 主方法 main

java">public static void main(String[] args) {Scanner sc = new Scanner(System.in);

• Scanner sc = new Scanner(System.in)：创建一个 Scanner 对象，用于从标准输入（控制台）读取数据。

---

3. 处理输入数据

java">Integer[] arr =Arrays.stream(sc.nextLine().split(" ")).map(p -> {int num = Integer.parseInt(p.substring(0, p.length() - 1));String unit = p.substring(p.length() - 1);return "Y".equals(unit) ? num : num * 7;}).toArray(Integer[]::new);

步骤解析：

1. 读取输入并分割字符串：

   • sc.nextLine()：读取用户输入的一行字符串。
   • split(" ")：将输入字符串按空格分割成字符串数组。例如，输入 "10Y 5D 7Y" 会被分割为 ["10Y", "5D", "7Y"]。

2. 将字符串数组转换为流：

   • Arrays.stream(...)：将字符串数组转换为流，方便后续操作。

3. 映射处理每个价格字符串：

   • map(p -> { ... })：对每个价格字符串 p 进行处理。
     • 提取数字部分：
       • p.substring(0, p.length() - 1)：去掉最后一个字符（单位），提取数字部分。例如，"10Y" 提取为 "10"。
       • Integer.parseInt(...)：将提取的数字部分转换为整数。例如，"10" 转换为 10。
     • 提取单位部分：
       • p.substring(p.length() - 1)：提取最后一个字符（单位）。例如，"10Y" 提取为 "Y"。
     • 根据单位转换价格：
       • 如果单位是 "Y"，则直接返回数字部分。
       • 如果单位是 "D"，则将数字部分乘以 7（假设 1 年 = 7 天）。

4. 将流转换为数组：

   • toArray(Integer[]::new)：将处理后的流转换为 Integer 数组。

---

4. 调用算法并输出结果

java">System.out.println(getResult(arr));

• getResult(arr)：调用 getResult 方法，传入处理后的价格数组 arr。
• System.out.println(...)：输出计算结果。

---

5. 算法入口 getResult

java">public static int getResult(Integer[] arr) {int ans = 0;for (int i = 1; i < arr.length; i++) {ans += Math.max(0, arr[i] - arr[i - 1]);}return ans;
}

功能说明：

• 计算价格数组中每个价格与前一个价格的差值，并将所有正差值累加。

步骤解析：

1. 初始化累加器 ans：

   • int ans = 0：用于存储累加结果。

2. 遍历价格数组：

   • for (int i = 1; i < arr.length; i++)：从第二个元素开始遍历数组。
     • 计算差值：
       • arr[i] - arr[i - 1]：计算当前价格与前一个价格的差值。
     • 累加正差值：
       • Math.max(0, ...)：如果差值为负数，则取 0；否则取差值本身。
       • ans += ...：将正差值累加到 ans 中。

3. 返回结果：

   • return ans：返回累加的正差值总和。

---

示例运行

输入：

10Y 5D 7Y

处理过程：

1. 分割输入：

   • 输入字符串 "10Y 5D 7Y" 被分割为 ["10Y", "5D", "7Y"]。

2. 转换价格：

   • "10Y" → 10（单位是 "Y"，直接返回）。
   • "5D" → 5 * 7 = 35（单位是 "D"，转换为年）。
   • "7Y" → 7（单位是 "Y"，直接返回）。
   • 转换后的数组为 [10, 35, 7]。

3. 计算正差值总和：

   • 35 - 10 = 25（正差值，累加到 ans）。
   • 7 - 35 = -28（负差值，不累加）。
   • 最终 ans = 25。

输出：

25

---

总结

• 该程序从控制台读取一行输入，将其分割为多个价格字符串。
• 根据价格的单位（Y 或 D）进行转换，统一为以年为单位的价格。
• 计算价格数组中每个价格与前一个价格的正差值，并累加这些正差值。
• 最终输出累加结果。

如果有其他问题，欢迎随时提问！

四、Python算法源码

python"># 输入获取
tmp = input().split()# 输入转换
def convert(s):# 将字符串s转换为数字和单位num = int(s[:-1])  # 提取数字部分，去掉最后一个字符（单位）unit = s[-1]  # 提取最后一个字符作为单位# 根据单位进行转换if unit == 'Y':return num  # 如果单位是'Y'，直接返回数字else:return num * 7  # 如果单位不是'Y'，则乘以7（假设单位是'W'，表示周）# 将输入列表中的每个元素通过convert函数进行转换
arr = list(map(convert, tmp))# 算法入口
def getResult():ans = 0  # 初始化结果变量for i in range(1, len(arr)):# 计算相邻两个元素的差值，如果差值大于0，则累加到结果中ans += max(0, arr[i] - arr[i - 1])return ans  # 返回最终结果# 算法调用
print(getResult())

代码讲解：

1. 输入获取：

   • tmp = input().split()：从标准输入获取一行输入，并将其按空格分割成一个列表tmp。例如，输入"10Y 20W 30Y"会被分割成['10Y', '20W', '30Y']。

2. 输入转换：

   • convert(s)函数用于将输入的字符串转换为数值。假设输入的字符串格式为数字+单位，例如10Y或20W。
     • num = int(s[:-1])：提取字符串中除最后一个字符外的部分，并将其转换为整数。例如，10Y中的10。
     • unit = s[-1]：提取字符串的最后一个字符作为单位。例如，10Y中的Y。
     • 如果单位是Y，则直接返回数字；如果单位是W（假设），则返回数字乘以7（表示将周转换为天）。

3. 转换列表：

   • arr = list(map(convert, tmp))：将tmp列表中的每个元素通过convert函数进行转换，并将结果存储在arr列表中。例如，['10Y', '20W', '30Y']会被转换为[10, 140, 30]。

4. 算法入口：

   • getResult()函数用于计算相邻两个元素的差值，并将所有大于0的差值累加。
     • ans = 0：初始化结果变量ans为0。
     • for i in range(1, len(arr))：遍历arr列表，从第二个元素开始。
     • ans += max(0, arr[i] - arr[i - 1])：计算当前元素与前一个元素的差值，如果差值大于0，则累加到ans中。
     • return ans：返回最终的计算结果。

5. 算法调用：

   • print(getResult())：调用getResult()函数并打印结果。

示例：

假设输入为"10Y 20W 30Y"，代码的执行过程如下：

1. tmp = ['10Y', '20W', '30Y']
2. arr = [10, 140, 30]
3. getResult()计算相邻差值：
   • 140 - 10 = 130（大于0，累加）
   • 30 - 140 = -110（小于0，不累加）
4. 最终结果为130，输出130。

希望这个详细的注释和讲解对您理解代码有所帮助！

五、C/C++算法源码：

C++ 代码

#include <iostream>
#include <vector>using namespace std;// 定义一个宏，用于计算两个数的最大值
#define MAX(a, b) ((a) > (b) ? (a) : (b))// 定义最大数组大小
const int MAX_SIZE = 10000;int main() {// 使用vector来存储收入数据，动态数组更安全vector<int> incomes;int num;char unit;// 循环读取输入，直到遇到非空格字符结束while (cin >> num >> unit) {// 根据单位（Y或W）将收入转换为统一单位（Y为1，W为7）incomes.push_back(num * (unit == 'Y' ? 1 : 7));// 如果下一个字符不是空格，则结束输入if (cin.get() != ' ') break;}int ans = 0;// 遍历收入数组，计算相邻收入的差值，并累加正差值for (size_t i = 1; i < incomes.size(); ++i) {ans += MAX(0, incomes[i] - incomes[i - 1]);}// 输出结果cout << ans << endl;return 0;
}

C 语言代码

#include <stdio.h>// 定义一个宏，用于计算两个数的最大值
#define MAX(a, b) ((a) > (b) ? (a) : (b))// 定义最大数组大小
#define MAX_SIZE 10000int main() {// 定义一个数组来存储收入数据int incomes[MAX_SIZE];int incomes_size = 0;int num;char unit;// 循环读取输入，直到遇到非空格字符结束while (scanf("%d%c", &num, &unit) == 2) {// 根据单位（Y或W）将收入转换为统一单位（Y为1，W为7）incomes[incomes_size] = num * (unit == 'Y' ? 1 : 7);incomes_size++;// 如果下一个字符不是空格，则结束输入if (getchar() != ' ') break;}int ans = 0;// 遍历收入数组，计算相邻收入的差值，并累加正差值for (int i = 1; i < incomes_size; i++) {ans += MAX(0, incomes[i] - incomes[i - 1]);}// 输出结果printf("%d\n", ans);return 0;
}

代码讲解

1. 宏定义 MAX(a, b):

   • 这个宏用于计算两个数的最大值。在C和C++中，宏是一种预处理指令，它在编译之前进行文本替换。MAX(a, b) 会被替换为 ((a) > (b) ? (a) : (b))，即如果 a 大于 b，则返回 a，否则返回 b。

2. 数组和输入处理:

   • 在C语言中，我们使用固定大小的数组 incomes[MAX_SIZE] 来存储收入数据，并通过 incomes_size 来记录当前数组的大小。
   • 在C++中，我们使用 vector<int> 来存储收入数据，vector 是C++标准库中的动态数组，可以根据需要自动调整大小，更加安全和灵活。

3. 输入循环:

   • 使用 while 循环不断读取输入，直到遇到非空格字符结束。scanf("%d%c", &num, &unit) 用于读取一个整数和一个字符，分别存储在 num 和 unit 中。
   • 根据 unit 的值（Y 或 W），将收入转换为统一单位（Y 为1，W 为7），并将其存储在 incomes 数组中。

4. 计算收入差值:

   • 遍历 incomes 数组，计算相邻收入的差值，并累加正差值。MAX(0, incomes[i] - incomes[i - 1]) 确保只累加正差值，忽略负差值。

5. 输出结果:

   • 最后，输出计算得到的结果。

总结

• C语言 和 C++ 代码的主要区别在于数据结构的处理方式。C语言使用固定大小的数组，而C++使用 vector 动态数组，后者更加安全和灵活。
• 代码的核心逻辑是读取输入、转换单位、计算差值并输出结果。通过宏定义和循环结构，代码简洁且高效。

希望这些解释对您有所帮助！如果有任何进一步的问题，请随时提问。

六、尾言

什么是华为OD？

华为OD（Outsourcing Developer，外包开发工程师）是华为针对软件开发工程师岗位的一种招聘形式，主要包括笔试、技术面试以及综合面试等环节。尤其在笔试部分，算法题的机试至关重要。

为什么刷题很重要？

1. 机试是进入技术面的第一关：
   华为OD机试（常被称为机考）主要考察算法和编程能力。只有通过机试，才能进入后续的技术面试环节。

2. 技术面试需要手撕代码：
   技术一面和二面通常会涉及现场编写代码或算法题。面试官会注重考察候选人的思路清晰度、代码规范性以及解决问题的能力。因此提前刷题、多练习是通过面试的重要保障。

3. 入职后的可信考试：
   入职华为后，还需要通过“可信考试”。可信考试分为三个等级：

   • 入门级：主要考察基础算法与编程能力。
   • 工作级：更贴近实际业务需求，可能涉及复杂的算法或与工作内容相关的场景题目。
   • 专业级：最高等级，考察深层次的算法以及优化能力，与薪资直接挂钩。

刷题策略与说明：

2024年8月14日之后，华为OD机试的题库转为 E卷，由往年题库（D卷、A卷、B卷、C卷）和全新题目组成。刷题时可以参考以下策略：

1. 关注历年真题：

   • 题库中的旧题占比较大，建议优先刷历年的A卷、B卷、C卷、D卷题目。
   • 对于每道题目，建议深度理解其解题思路、代码实现，以及相关算法的适用场景。

2. 适应新题目：

   • E卷中包含全新题目，需要掌握全面的算法知识和一定的灵活应对能力。
   • 建议关注新的刷题平台或交流群，获取最新题目的解析和动态。

3. 掌握常见算法：
   华为OD考试通常涉及以下算法和数据结构：

   • 排序算法（快速排序、归并排序等）
   • 动态规划（背包问题、最长公共子序列等）
   • 贪心算法
   • 栈、队列、链表的操作
   • 图论（最短路径、最小生成树等）
   • 滑动窗口、双指针算法

4. 保持编程规范：

   • 注重代码的可读性和注释的清晰度。
   • 熟练使用常见编程语言，如C++、Java、Python等。

如何获取资源？

1. 官方参考：

   • 华为招聘官网或相关的招聘平台会有一些参考信息。
   • 华为OD的相关公众号可能也会发布相关的刷题资料或学习资源。

2. 加入刷题社区：

   • 找到可信的刷题交流群，与其他备考的小伙伴交流经验。
   • 关注知名的刷题网站，如LeetCode、牛客网等，这些平台上有许多华为OD的历年真题和解析。

3. 寻找系统性的教程：

   • 学习一本经典的算法书籍，例如《算法导论》《剑指Offer》《编程之美》等。
   • 完成系统的学习课程，例如数据结构与算法的在线课程。

积极心态与持续努力：

刷题的过程可能会比较枯燥，但它能够显著提升编程能力和算法思维。无论是为了通过华为OD的招聘考试，还是为了未来的职业发展，这些积累都会成为重要的财富。

考试注意细节

1. 本地编写代码

   • 在本地 IDE（如 VS Code、PyCharm 等）上编写、保存和调试代码，确保逻辑正确后再复制粘贴到考试页面。这样可以减少语法错误，提高代码准确性。

2. 调整心态，保持冷静

   • 遇到提示不足或实现不确定的问题时，不必慌张，可以采用更简单或更有把握的方法替代，确保思路清晰。

3. 输入输出完整性

   • 注意训练和考试时都需要编写完整的输入输出代码，尤其是和题目示例保持一致。完成代码后务必及时调试，确保功能符合要求。

4. 快捷键使用

   • 删除行可用 Ctrl+D，复制、粘贴和撤销分别为 Ctrl+C，Ctrl+V，Ctrl+Z，这些可以正常使用。
   • 避免使用 Ctrl+S，以免触发浏览器的保存功能。

5. 浏览器要求

   • 使用最新版的 Google Chrome 浏览器完成考试，确保摄像头开启并正常工作。考试期间不要切换到其他网站，以免影响考试成绩。

6. 交卷相关

   • 答题前，务必仔细查看题目示例，避免遗漏要求。
   • 每完成一道题后，点击【保存并调试】按钮，多次保存和调试是允许的，系统会记录得分最高的一次结果。完成所有题目后，点击【提交本题型】按钮。
   • 确保在考试结束前提交试卷，避免因未保存或调试失误而丢分。

7. 时间和分数安排

   • 总时间：150 分钟；总分：400 分。
   • 试卷结构：2 道一星难度题（每题 100 分），1 道二星难度题（200 分）。及格分为 150 分。合理分配时间，优先完成自己擅长的题目。

8. 考试环境准备

   • 考试前请备好草稿纸和笔。考试中尽量避免离开座位，确保监控画面正常。
   • 如需上厕所，请提前规划好时间以减少中途离开监控的可能性。

9. 技术问题处理

   • 如果考试中遇到断电、断网、死机等技术问题，可以关闭浏览器并重新打开试卷链接继续作答。
   • 出现其他问题，请第一时间联系 HR 或监考人员进行反馈。

祝你考试顺利，取得理想成绩！