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

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

article 2024/11/5 11:37:46

在这里插入图片描述

华为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)):
        # 更新 maxEndingHere
        max_ending_here = max(profit[i], max_ending_here + profit[i])
        # 更新 maxSoFar
        max_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++) {
        // 更新 maxEndingHere
        maxEndingHere = Math.max(profit[i], maxEndingHere + profit[i]);
        // 更新 maxSoFar
        maxSoFar = 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++) {
        // 更新 maxEndingHere
        max_ending_here = (profit[i] > max_ending_here + profit[i]) ? profit[i] : max_ending_here + profit[i];
        // 更新 maxSoFar
        if (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++) {
        // 更新 maxEndingHere
        maxEndingHere = max(profit[i], maxEndingHere + profit[i]);
        // 更新 maxSoFar
        maxSoFar = 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;
}