当前位置：首页 > news >正文

华为OD机试 - 连续天数的最高利润额 - 动态规划（Python/JS/C/C++ 2024 C卷 100分）

news 2024/11/5 11:38:25

在这里插入图片描述

华为OD机试 2024E卷题库疯狂收录中，刷题点这里

专栏导读

本专栏收录于《华为OD机试真题（Python/JS/C/C++）》。

刷的越多，抽中的概率越大，私信哪吒，备注华为OD，加入华为OD刷题交流群，每一题都有详细的答题思路、详细的代码注释、3个测试用例、为什么这道题采用XX算法、XX算法的适用场景，发现新题目，随时更新。

一、题目描述

公司每日盈利的利润额记于整数数组 profit，请返回连续一或多天利润额总和的最高值。

二、输入描述

第一行为一个整数，表示天数

第二行为整数列表，分别为每日的利润。

三、输出描述

输出整数，表示连续天数利润额总和的最高值。

1、输入

4
2 3 -5 4

2、输出

3、说明

"2 3”连续2天的利润总额总和为最高值，连续利润额为5。

四、测试用例

1、输入

10
2 3 -5 4 2 0 0 1 -2 8

2、输出

五、解题思路

这道题的目的是在给定的利润数组中，找到连续子数组的最大和，要解决这个问题，我们可以采用动态规划的思想。

最大连续子数组和问题可以被分解为若干子问题。具体来说，求解以第 i 个元素结尾的最大子数组和，依赖于求解以第 i-1 个元素结尾的最大子数组和。

这种重叠子问题的性质使得动态规划成为一种非常合适的解题方法，因为动态规划能够通过记住（缓存）子问题的结果来避免重复计算。

读取输入的天数和每日的利润数组。
初始化 maxEndingHere 和 maxSoFar 为利润数组的第一个元素。
通过迭代数组，从第二个元素开始，逐步更新 maxEndingHere 和 maxSoFar。
最终，maxSoFar 即为最大连续利润和。

复杂度分析

时间复杂度: O(n)，其中 n 是利润数组的长度。算法只需一次遍历数组，因此时间复杂度为线性。

空间复杂度: O(1)，只使用了固定数量的额外空间（maxEndingHere 和 maxSoFar），空间复杂度为常数。

六、Python算法源码

def find_max_profit(profit):# 初始化 maxEndingHere 和 maxSoFar 为利润数组的第一个元素max_ending_here = profit[0]max_so_far = profit[0]# 遍历利润数组，从第二个元素开始for i in range(1, len(profit)):# 更新 maxEndingHeremax_ending_here = max(profit[i], max_ending_here + profit[i])# 更新 maxSoFarmax_so_far = max(max_so_far, max_ending_here)return max_so_far# 读取天数
days = int(input())
# 读取每日利润
profit = list(map(int, input().split()))# 输出结果
print(find_max_profit(profit))

七、JavaScript算法源码

function findMaxProfit(profit) {// 初始化 maxEndingHere 和 maxSoFar 为利润数组的第一个元素let maxEndingHere = profit[0];let maxSoFar = profit[0];// 遍历利润数组，从第二个元素开始for (let i = 1; i < profit.length; i++) {// 更新 maxEndingHeremaxEndingHere = Math.max(profit[i], maxEndingHere + profit[i]);// 更新 maxSoFarmaxSoFar = Math.max(maxSoFar, maxEndingHere);}return maxSoFar;
}// 读取天数
let days = parseInt(prompt());
let profit = prompt().split(" ").map(Number);// 输出结果
console.log(findMaxProfit(profit));

八、C算法源码

#include <stdio.h>int find_max_profit(int profit[], int days) {// 初始化 maxEndingHere 和 maxSoFar 为利润数组的第一个元素int max_ending_here = profit[0];int max_so_far = profit[0];// 遍历利润数组，从第二个元素开始for (int i = 1; i < days; i++) {// 更新 maxEndingHeremax_ending_here = (profit[i] > max_ending_here + profit[i]) ? profit[i] : max_ending_here + profit[i];// 更新 maxSoFarif (max_ending_here > max_so_far) {max_so_far = max_ending_here;}}return max_so_far;
}int main() {int days;// 读取天数scanf("%d", &days);int profit[days];// 读取每日利润for (int i = 0; i < days; i++) {scanf("%d", &profit[i]);}// 输出结果printf("%d\n", find_max_profit(profit, days));return 0;
}

九、C++算法源码

#include <iostream>
#include <vector>
using namespace std;int findMaxProfit(const vector<int>& profit) {// 初始化 maxEndingHere 和 maxSoFar 为利润数组的第一个元素int maxEndingHere = profit[0];int maxSoFar = profit[0];// 遍历利润数组，从第二个元素开始for (size_t i = 1; i < profit.size(); i++) {// 更新 maxEndingHeremaxEndingHere = max(profit[i], maxEndingHere + profit[i]);// 更新 maxSoFarmaxSoFar = max(maxSoFar, maxEndingHere);}return maxSoFar;
}int main() {int days;// 读取天数cin >> days;vector<int> profit(days);// 读取每日利润for (int i = 0; i < days; i++) {cin >> profit[i];}// 输出结果cout << findMaxProfit(profit) << endl;return 0;
}