华为OD笔试之【DP/贪心】双机位A-贪心的商人【Py/Java/C++/C/JS/Go六种语言OD独家双机位A卷真题】【欧弟算法】全网注释最详细分类最全的华子OD真题题解

闭着眼睛学算法

1065人浏览 · 2025-09-18 18:03:04

闭着眼睛学算法 · 2025-09-18 18:03:04 发布

可上欧弟OJ系统练习华子OD、大厂真题
绿色聊天软件戳 od1441了解算法冲刺训练（备注【CSDN】否则不通过）

题目描述与示例

题目描述

商人经营一家店铺，有 number 种商品，由于仓库限制每件商品的最大持有数量是 item[index]，每种商品的价格在每天是 item_price[item_index][day]，通过对商品的买进和卖出获取利润，请给出商人在 days 天内能获取到的最大的利润；

注：同一件商品可以反复买进和卖出；

输入描述

3     // 输入商品的数量 number
3     // 输入商人售货天数 days
4 5 6 // 输入仓库限制每件商品的最大持有数量是 item[index]
1 2 3 // 输入第一件商品每天的价格
4 3 2 // 输入第二件商品每天的价格
1 5 3 // 输入第三件商品每天的价格

输出描述

32     // 输出商人在这段时间内的最大利润

说明

根据输入的信息： number = 3，days = 3，item = [4，5，6]，item_price = [[1，2，3]，[4，3，2]，[1，5，3]]。

针对第一件商品，商人在第一天的价格是 item_price[0][0] = 1 时买入 item[0]件，在第三天 item_price[0][2] = 3 的时候卖出，获利最大是 8；
针对第二件商品，不进行交易，获利最大是 0；
针对第三件商品，商人在第一天的价格是 item_price[2][0] = 1 时买入 item[2]件，在第二天 item_price[2][0] == 5 的时候卖出，获利最大是 24；

因此这段时间商人能获取的最大利润是 8 + 24 = 32；

示例

输入

输出

解题思路

注意，本题的核心逻辑和LC122. 买卖股票的最佳时机II完全一致。

注意到各种商品之间是相互独立的，即第i件商品的买卖与第j件商品的买卖无关。因此对于每一种商品我们都可以单独计算其利润，再将利润加总即可。

又注意到对于某特定商品而言，存在关系总利润 = 数量 × 单件利润。故我们仅需计算某商品单件能取得的最大利润，再直接乘以每件商品的最大库存数number[i]即为该种商品能取得的总利润。

计算单件商品最大利润的核心代码完全无需修改，不管用贪心还是动态规划，假设我们已经成功定义了函数maxProfit()，那么上述逻辑整理为代码即

n = int(input())
days = int(input())
numbers = list(map(int, input().split()))

ans = 0
for i in range(n):
    prices = list(map(int, input().split()))
    ans += maxProfit(prices, days) * numbers[i]

print(ans)

代码

解法一：贪心

Python

# 欢迎来到「欧弟算法 - 华为OD全攻略」,收录华为OD题库、面试指南、八股文与学员案例！
# 地址：https://www.odalgo.com
# 华为OD机试刷题网站：https://www.algomooc.com
# 添加微信 278166530 获取华为 OD 笔试真题题库和视频

# 题目：2025A/2025B/双机位A-贪心的商人
# 分值：100
# 作者：闭着眼睛学数理化
# 算法：贪心
# 代码看不懂的地方，请直接在群上提问


# 计算某个特定商品能取得的最大利润的函数
# 和LeetCode122. 买卖股票的最佳时机II完全一致
def maxProfit(prices, days):
    # 最大利润初始为 0
    profit = 0

    # 从第 2 天开始（索引为 1）
    # 去查看当天是否需要采取【卖出】的操作
    for i in range(1, days):

        # 计算当天的股票价格与昨天的股票价格的差值
        tmp = prices[i] - prices[i - 1]

        # 如果发现当天的股票价格大于了昨天的股票价格
        # 那么在当天采取【卖出】操作可以带来正向收益，即产生利润
        # 于是完全可以卖出
        # 而这个利润就可以进行累加起来
        if tmp > 0:
            profit += tmp

        # 如果发现当天的股票价格小于了昨天的股票价格
        # 那么不能采取【卖出】操作，因为这会带来负向收益，即产生亏损
        # 导致总的利润值变小

    # 返回结果
    return profit

# 输入商品数量
n = int(input())
# 输入天数
days = int(input())
# 输入每种商品的最大数目
numbers = list(map(int, input().split()))

# 初始化答案变量
ans = 0
# 循环n次，输入每种商品在days天中的价格变化
for i in range(n):
    prices = list(map(int, input().split()))
    # maxProfit(prices, days)返回单件第i种商品能够取得的最大利润
    # 再乘上numbers[i]即为能够获得第i种商品能够获得的总利润
    ans += maxProfit(prices, days) * numbers[i]

print(ans)

Java

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);

        int n = input.nextInt();
        int days = input.nextInt();

        int[] numbers = new int[n];
        for (int i = 0; i < n; i++) {
            numbers[i] = input.nextInt();
        }

        int ans = 0;
        for (int i = 0; i < n; i++) {
            int[] prices = new int[days];
            for (int j = 0; j < days; j++) {
                prices[j] = input.nextInt();
            }
            ans += maxProfit(prices) * numbers[i];
        }

        System.out.println(ans);
    }

    public static int maxProfit(int[] prices) {
        int profit = 0;

        for (int i = 1; i < prices.length; i++) {
            int tmp = prices[i] - prices[i - 1];
            if (tmp > 0) {
                profit += tmp;
            }
        }

        return profit;
    }
}

C++

#include <iostream>
#include <vector>
using namespace std;

int maxProfit(const vector<int>& prices) {
    int profit = 0;

    for (int i = 1; i < prices.size(); i++) {
        int tmp = prices[i] - prices[i - 1];
        if (tmp > 0) {
            profit += tmp;
        }
    }

    return profit;
}

int main() {
    int n, days;
    cin >> n >> days;

    vector<int> numbers(n);
    for (int i = 0; i < n; i++) {
        cin >> numbers[i];
    }

    int ans = 0;
    for (int i = 0; i < n; i++) {
        vector<int> prices(days);
        for (int j = 0; j < days; j++) {
            cin >> prices[j];
        }
        ans += maxProfit(prices) * numbers[i];
    }

    cout << ans << endl;

    return 0;
}

C

#include <stdio.h>

// 计算某个特定商品能取得的最大利润的函数
int maxProfit(int prices[], int days) {
    int profit = 0;

    // 从第2天开始，查看当天是否采取【卖出】操作
    for (int i = 1; i < days; i++) {
        int tmp = prices[i] - prices[i - 1];
        
        // 如果当天价格大于昨天，则可以卖出
        if (tmp > 0) {
            profit += tmp;
        }
    }
    return profit;
}

int main() {
    int n, days;

    // 输入商品数量
    scanf("%d", &n);

    // 输入天数
    scanf("%d", &days);

    // 输入每种商品的最大数目
    int numbers[n];
    for (int i = 0; i < n; i++) {
        scanf("%d", &numbers[i]);
    }

    int ans = 0;
    // 循环n次，输入每种商品的价格变化
    for (int i = 0; i < n; i++) {
        int prices[days];
        for (int j = 0; j < days; j++) {
            scanf("%d", &prices[j]);
        }

        // 计算单件第i种商品的最大利润并累加总利润
        ans += maxProfit(prices, days) * numbers[i];
    }

    printf("%d\n", ans);
    return 0;
}

Node JavaScript

const readline = require("readline");

// 创建读取接口
const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout
});

let input = [];
rl.on("line", (line) => {
    input.push(line.trim());
}).on("close", () => {
    // 输入处理
    const n = parseInt(input[0]); // 商品数量
    const days = parseInt(input[1]); // 天数
    const numbers = input[2].split(" ").map(Number); // 每种商品的最大数目

    // 计算某个特定商品能取得的最大利润的函数
    const maxProfit = (prices, days) => {
        let profit = 0;
        for (let i = 1; i < days; i++) {
            const tmp = prices[i] - prices[i - 1];
            if (tmp > 0) {
                profit += tmp;
            }
        }
        return profit;
    };

    let ans = 0;
    for (let i = 0; i < n; i++) {
        const prices = input[3 + i].split(" ").map(Number);
        // 计算并累加每种商品的总利润
        ans += maxProfit(prices, days) * numbers[i];
    }

    console.log(ans);
});

Go

package main

import (
    "bufio"
    "fmt"
    "os"
    "strconv"
    "strings"
)

// 计算某个特定商品能取得的最大利润的函数
func maxProfit(prices []int, days int) int {
    profit := 0
    for i := 1; i < days; i++ {
        tmp := prices[i] - prices[i-1]
        if tmp > 0 {
            profit += tmp
        }
    }
    return profit
}

func main() {
    reader := bufio.NewReader(os.Stdin)
    
    // 输入商品数量
    nStr, _ := reader.ReadString('\n')
    n, _ := strconv.Atoi(strings.TrimSpace(nStr))
    
    // 输入天数
    daysStr, _ := reader.ReadString('\n')
    days, _ := strconv.Atoi(strings.TrimSpace(daysStr))

    // 输入每种商品的最大数目
    numbersStr, _ := reader.ReadString('\n')
    numbersStrArr := strings.Fields(strings.TrimSpace(numbersStr))
    numbers := make([]int, n)
    for i := 0; i < n; i++ {
        numbers[i], _ = strconv.Atoi(numbersStrArr[i])
    }

    ans := 0
    for i := 0; i < n; i++ {
        pricesStr, _ := reader.ReadString('\n')
        pricesStrArr := strings.Fields(strings.TrimSpace(pricesStr))
        
        // 将字符串数组转换为整数数组
        prices := make([]int, days)
        for j := 0; j < days; j++ {
            prices[j], _ = strconv.Atoi(pricesStrArr[j])
        }

        // 计算单件第i种商品的最大利润并累加总利润
        ans += maxProfit(prices, days) * numbers[i]
    }

    fmt.Println(ans)
}

时空复杂度

时间复杂度：O(NM)。需要循环N种商品，每次都要遍历M天来计算最大利润。

空间复杂度：O(1)。无需额外空间储存数据。

解法二：dp（吴师兄股票问题模板写法）

Python

# 欢迎来到「欧弟算法 - 华为OD全攻略」,收录华为OD题库、面试指南、八股文与学员案例！
# 地址：https://www.odalgo.com
# 华为OD机试刷题网站：https://www.algomooc.com
# 添加微信 278166530 获取华为 OD 笔试真题题库和视频

# 题目：2025A/2025B/双机位A-贪心的商人
# 分值：100
# 作者：闭着眼睛学数理化
# 算法：动态规划
# 代码看不懂的地方，请直接在群上提问


# 计算某个特定商品能取得的最大利润的函数
# 和LeetCode122. 买卖股票的最佳时机II完全一致
def maxProfit(prices, days):
    # 设置一个三维数组 dp
    # dp[i][k][b]
    # i 表示天数，dp[i] 表示第 i 天的最大利润
    # k 表示最多交易次数，每次交易包含买入和卖出，这里只在买入的时候将 k - 1
    # 注意：【 k 表示最多交易次数，而不是实际交易次数，比如最多交易两次可能实际只交易一次】
    # b 表示当前是否持有股票，取值为 0 和 1
    # 其中 0 表示当前持有 0 份股票，即【不持有】股票
    # 而 1 表示当前持有 1 份股票，即【持有】股票

    # 在本题中，k 的值为正无穷，因此可以不设置这个维度
    # i 的取值范围为数组 prices 的长度，从 0 开始

    # 构建长度为n*2的dp数组
    # dp[i]表示第i天的情况
    # dp[i][0]表示在第i天如果持有0份股票的最大利润
    # dp[i][1]表示在第i天如果持有1份股票的最大利润
    dp = [[0] * 2 for _ in range(days)]

    # dp[0][0][0] 表示在第 0 天结束时，即收盘后，手上持有 0 份股票，且此时最多进行了 0 次交易的情况下可以获得的最大收益
    # 此时，就是什么都没做，利润为 0

    # dp[0][k][0] 表示在第 0 天结束时，即收盘后，手上持有 0 份股票，且此时最多进行了 k 次交易的情况下可以获得的最大收益
    # 此时，就是什么都没做，利润为 0
    dp[0][0] = 0

    # dp[0][k][1] 表示在第 0 天结束时，即收盘后，手上持有 1 份股票，且此时最多进行了 k 次交易的情况下可以获得的最大收益
    # 手上持有了 1 份股票，那肯定是执行了买入操作，然后又还没有卖出，那么钱都投入了股票中，利润就是负的，即为 -prices[0]
    dp[0][1] = -prices[0]

    # 动态规划：自底向上，即从前向后遍历，实现一个萝卜一个坑
    for i in range(1, days):
        # 对于每个坑来说，都有两种状态
        # 今天也就是第 i 天

        # 1、今天【不持有】股票
        # 第 i - 1 天【持有】股票，第 i 天卖出
        # 昨天【持有】股票，今天卖出
        # vs
        # 第 i - 1 天【不持有】股票，第 i 天不操作
        # 昨天【不持有】股票，今天不操作
        dp[i][0] = max(dp[i-1][0], dp[i - 1][1] + prices[i])

        # 2、今天【持有】股票
        # 第 i - 1 天【持有】股票，第 i 天不操作
        # 昨天【持有】股票，今天不操作
        # vs
        # 第 i - 1 天【不持有】股票，第 i 天买入
        # 昨天【不持有】股票，今天买入
        dp[i][1] = max(dp[i-1][1], dp[i-1][0] - prices[i])

    # for 循环结束后，dp 数组填充完毕
    # dp[days-1][k][0]
    # 表示第 days - 1 天结束时，即最后一天收盘后，
    # 手上持有 0 份股票，可以获得的最大收益
    return dp[days-1][0]

# 输入商品数量
n = int(input())
# 输入天数
days = int(input())
# 输入每种商品的最大数目
numbers = list(map(int, input().split()))

# 初始化答案变量
ans = 0
# 循环n次，输入每种商品在days天中的价格变化
for i in range(n):
    prices = list(map(int, input().split()))
    # maxProfit(prices, days)返回单件第i种商品能够取得的最大利润
    # 再乘上numbers[i]即为能够获得第i种商品能够获得的总利润
    ans += maxProfit(prices, days) * numbers[i]

print(ans)

Java

import java.util.Scanner;

public class Main {

    // 计算某个特定商品能取得的最大利润的函数
    public static int maxProfit(int[] prices, int days) {
        // 构建一个二维数组 dp
        // dp[i][0] 表示在第 i 天不持有股票的最大利润
        // dp[i][1] 表示在第 i 天持有股票的最大利润
        int[][] dp = new int[days][2];
        
        // 第一天的初始化状态
        dp[0][0] = 0;
        dp[0][1] = -prices[0];

        // 动态规划，逐天计算
        for (int i = 1; i < days; i++) {
            // 今天不持有股票
            dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
            // 今天持有股票
            dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
        }

        // 返回最后一天不持有股票的最大利润
        return dp[days - 1][0];
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        // 输入商品数量
        int n = scanner.nextInt();
        // 输入天数
        int days = scanner.nextInt();
        
        // 输入每种商品的最大数目
        int[] numbers = new int[n];
        for (int i = 0; i < n; i++) {
            numbers[i] = scanner.nextInt();
        }

        int ans = 0;
        // 循环输入每种商品的价格变化
        for (int i = 0; i < n; i++) {
            int[] prices = new int[days];
            for (int j = 0; j < days; j++) {
                prices[j] = scanner.nextInt();
            }
            // 计算单件商品的最大利润并乘以数量
            ans += maxProfit(prices, days) * numbers[i];
        }

        System.out.println(ans);
        scanner.close();
    }
}

C++

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// 计算某个特定商品能取得的最大利润的函数
int maxProfit(const vector<int>& prices, int days) {
    // 构建一个二维数组 dp
    // dp[i][0] 表示在第 i 天不持有股票的最大利润
    // dp[i][1] 表示在第 i 天持有股票的最大利润
    vector<vector<int>> dp(days, vector<int>(2, 0));

    // 第一天的初始化状态
    dp[0][0] = 0;
    dp[0][1] = -prices[0];

    // 动态规划，逐天计算
    for (int i = 1; i < days; i++) {
        // 今天不持有股票
        dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
        // 今天持有股票
        dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
    }

    // 返回最后一天不持有股票的最大利润
    return dp[days - 1][0];
}

int main() {
    int n, days;
    // 输入商品数量
    cin >> n;
    // 输入天数
    cin >> days;

    // 输入每种商品的最大数目
    vector<int> numbers(n);
    for (int i = 0; i < n; i++) {
        cin >> numbers[i];
    }

    int ans = 0;
    // 循环输入每种商品的价格变化
    for (int i = 0; i < n; i++) {
        vector<int> prices(days);
        for (int j = 0; j < days; j++) {
            cin >> prices[j];
        }
        // 计算单件商品的最大利润并乘以数量
        ans += maxProfit(prices, days) * numbers[i];
    }

    cout << ans << endl;

    return 0;
}

C

#include <stdio.h>
#include <stdlib.h>

// 计算某个特定商品能取得的最大利润的函数
int maxProfit(int* prices, int days) {
    // 构建二维数组 dp
    // dp[i][0] 表示在第 i 天不持有股票的最大利润
    // dp[i][1] 表示在第 i 天持有股票的最大利润
    int dp[days][2];
    
    // 第一天的初始化状态
    dp[0][0] = 0;
    dp[0][1] = -prices[0];

    // 动态规划，逐天计算
    for (int i = 1; i < days; i++) {
        // 今天不持有股票
        dp[i][0] = (dp[i - 1][0] > dp[i - 1][1] + prices[i]) ? dp[i - 1][0] : dp[i - 1][1] + prices[i];
        // 今天持有股票
        dp[i][1] = (dp[i - 1][1] > dp[i - 1][0] - prices[i]) ? dp[i - 1][1] : dp[i - 1][0] - prices[i];
    }

    // 返回最后一天不持有股票的最大利润
    return dp[days - 1][0];
}

int main() {
    int n, days;
    // 输入商品数量和天数
    scanf("%d %d", &n, &days);

    // 输入每种商品的最大数目
    int* numbers = (int*)malloc(n * sizeof(int));
    for (int i = 0; i < n; i++) {
        scanf("%d", &numbers[i]);
    }

    int ans = 0;
    // 循环输入每种商品的价格变化
    for (int i = 0; i < n; i++) {
        int* prices = (int*)malloc(days * sizeof(int));
        for (int j = 0; j < days; j++) {
            scanf("%d", &prices[j]);
        }
        // 计算单件商品的最大利润并乘以数量
        ans += maxProfit(prices, days) * numbers[i];
        free(prices);
    }

    printf("%d\n", ans);
    free(numbers);
    return 0;
}

Node JavaScript

const readline = require('readline');

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

// 计算某个特定商品能取得的最大利润的函数
function maxProfit(prices, days) {
    // 构建长度为 days * 2 的二维数组 dp
    // dp[i][0] 表示在第 i 天如果不持有股票的最大利润
    // dp[i][1] 表示在第 i 天如果持有股票的最大利润
    const dp = Array.from({ length: days }, () => [0, 0]);

    dp[0][0] = 0;           // 第一天不持有股票，利润为 0
    dp[0][1] = -prices[0];  // 第一天持有股票，利润为 -prices[0]

    // 动态规划
    for (let i = 1; i < days; i++) {
        dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);  // 不持有股票
        dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i]);  // 持有股票
    }

    return dp[days - 1][0];  // 返回最后一天不持有股票的最大利润
}

let n, days;
let numbers = [];
let ans = 0;
let lineCount = 0;

rl.on('line', (line) => {
    if (lineCount === 0) {
        n = parseInt(line);
    } else if (lineCount === 1) {
        days = parseInt(line);
    } else if (lineCount === 2) {
        numbers = line.split(' ').map(Number);
    } else {
        const prices = line.split(' ').map(Number);
        ans += maxProfit(prices, days) * numbers[lineCount - 3];
    }
    lineCount++;

    if (lineCount === n + 3) {
        console.log(ans);
        rl.close();
    }
});

Go

package main

import (
    "bufio"
    "fmt"
    "os"
    "strconv"
    "strings"
)

// 计算某个特定商品能取得的最大利润的函数
func maxProfit(prices []int, days int) int {
    dp := make([][2]int, days)

    dp[0][0] = 0           // 第一天不持有股票，利润为 0
    dp[0][1] = -prices[0]  // 第一天持有股票，利润为 -prices[0]

    // 动态规划
    for i := 1; i < days; i++ {
        dp[i][0] = max(dp[i-1][0], dp[i-1][1]+prices[i]) // 不持有股票
        dp[i][1] = max(dp[i-1][1], dp[i-1][0]-prices[i]) // 持有股票
    }

    return dp[days-1][0]  // 返回最后一天不持有股票的最大利润
}

// 最大值计算函数
func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

func main() {
    scanner := bufio.NewScanner(os.Stdin)

    // 输入商品数量
    scanner.Scan()
    n, _ := strconv.Atoi(scanner.Text())

    // 输入天数
    scanner.Scan()
    days, _ := strconv.Atoi(scanner.Text())

    // 输入每种商品的最大数目
    scanner.Scan()
    numbersStr := strings.Split(scanner.Text(), " ")
    numbers := make([]int, n)
    for i := 0; i < n; i++ {
        numbers[i], _ = strconv.Atoi(numbersStr[i])
    }

    ans := 0
    // 循环输入每种商品的价格变化
    for i := 0; i < n; i++ {
        scanner.Scan()
        pricesStr := strings.Split(scanner.Text(), " ")
        prices := make([]int, days)
        for j := 0; j < days; j++ {
            prices[j], _ = strconv.Atoi(pricesStr[j])
        }
        // 计算单件商品的最大利润并乘以数量
        ans += maxProfit(prices, days) * numbers[i]
    }

    fmt.Println(ans)
}

时空复杂度

时间复杂度：O(NM)。需要循环N种商品，每次都要遍历M天来计算最大利润。

空间复杂度：O(M)。dp数组所占空间，为天数M。

*解法三：dp（许老师滚动dp数组写法）

Python

# 欢迎来到「欧弟算法 - 华为OD全攻略」,收录华为OD题库、面试指南、八股文与学员案例！
# 地址：https://www.odalgo.com
# 华为OD机试刷题网站：https://www.algomooc.com
# 添加微信 278166530 获取华为 OD 笔试真题题库和视频

# 题目：2025A-贪心的商人
# 分值：100
# 作者：闭着眼睛学数理化
# 算法：动态规划
# 代码看不懂的地方，请直接在群上提问


# 计算某个特定商品能取得的最大利润的函数
# 和LeetCode122. 买卖股票的最佳时机II完全一致
def maxProfit(prices, days):
    # 两种状态均表示第i天已经能够得到的最大利润
    # dp[0]: 持有股票
    # dp[1]: 没持有股票
    dp = [-prices[0], 0]
    for p in prices[1:]:
        dp = [max(dp[0], dp[1]-p),   # 今天持有 = max(今天之前买入的，之前持有-之前不买今天买)
              max(dp[1], p+dp[0])]      # 今天没持有 = max(今天之前卖出，今天卖出) 
    return dp[1]

# 输入商品数量
n = int(input())
# 输入天数
days = int(input())
# 输入每种商品的最大数目
numbers = list(map(int, input().split()))

# 初始化答案变量
ans = 0
# 循环n次，输入每种商品在days天中的价格变化
for i in range(n):
    prices = list(map(int, input().split()))
    # maxProfit(prices, days)返回单件第i种商品能够取得的最大利润
    # 再乘上numbers[i]即为能够获得第i种商品能够获得的总利润
    ans += maxProfit(prices, days) * numbers[i]

print(ans)

Java

import java.util.Scanner;

public class Main {

    // 计算某个特定商品能取得的最大利润的函数
    // 动态规划实现，与LeetCode 122类似
    public static int maxProfit(int[] prices, int days) {
        // 两种状态均表示第i天已经能够得到的最大利润
        // dp[0]: 持有股票
        // dp[1]: 没持有股票
        int[] dp = new int[]{-prices[0], 0};

        for (int i = 1; i < days; i++) {
            int p = prices[i];
            dp = new int[]{
                Math.max(dp[0], dp[1] - p),  // 今天持有 = max(之前持有, 今天买入)
                Math.max(dp[1], dp[0] + p)   // 今天没持有 = max(之前没持有, 今天卖出)
            };
        }
        return dp[1];
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        // 输入商品数量
        int n = scanner.nextInt();

        // 输入天数
        int days = scanner.nextInt();

        // 输入每种商品的最大数目
        int[] numbers = new int[n];
        for (int i = 0; i < n; i++) {
            numbers[i] = scanner.nextInt();
        }

        // 初始化答案变量
        int ans = 0;

        // 循环n次，输入每种商品在days天中的价格变化
        for (int i = 0; i < n; i++) {
            int[] prices = new int[days];
            for (int j = 0; j < days; j++) {
                prices[j] = scanner.nextInt();
            }

            // 计算每种商品的总利润并累加到ans
            ans += maxProfit(prices, days) * numbers[i];
        }

        System.out.println(ans);
        scanner.close();
    }
}

C++

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// 计算某个特定商品能取得的最大利润的函数
// 动态规划实现，与LeetCode 122类似
int maxProfit(const vector<int>& prices, int days) {
    // 两种状态均表示第i天已经能够得到的最大利润
    // dp[0]: 持有股票
    // dp[1]: 没持有股票
    vector<int> dp = {-prices[0], 0};

    for (int i = 1; i < days; i++) {
        int p = prices[i];
        dp = {
            max(dp[0], dp[1] - p),  // 今天持有 = max(之前持有, 今天买入)
            max(dp[1], dp[0] + p)   // 今天没持有 = max(之前没持有, 今天卖出)
        };
    }
    return dp[1];
}

int main() {
    int n, days;
    // 输入商品数量
    cin >> n;
    // 输入天数
    cin >> days;

    // 输入每种商品的最大数目
    vector<int> numbers(n);
    for (int i = 0; i < n; i++) {
        cin >> numbers[i];
    }

    // 初始化答案变量
    int ans = 0;

    // 循环n次，输入每种商品在days天中的价格变化
    for (int i = 0; i < n; i++) {
        vector<int> prices(days);
        for (int j = 0; j < days; j++) {
            cin >> prices[j];
        }

        // 计算每种商品的总利润并累加到ans
        ans += maxProfit(prices, days) * numbers[i];
    }

    cout << ans << endl;

    return 0;
}

C

#include <stdio.h>
#include <stdlib.h>

// 计算某个特定商品能取得的最大利润的函数
// 动态规划实现，与LeetCode 122类似
int maxProfit(int *prices, int days) {
    // 两种状态均表示第i天已经能够得到的最大利润
    // dp[0]: 持有股票
    // dp[1]: 没持有股票
    int dp[2] = {-prices[0], 0};

    for (int i = 1; i < days; i++) {
        int p = prices[i];
        int newDp[2] = {
            dp[0] > (dp[1] - p) ? dp[0] : (dp[1] - p), // 今天持有 = max(之前持有, 今天买入)
            dp[1] > (dp[0] + p) ? dp[1] : (dp[0] + p)  // 今天没持有 = max(之前没持有, 今天卖出)
        };
        dp[0] = newDp[0];
        dp[1] = newDp[1];
    }
    return dp[1];
}

int main() {
    int n, days;
    // 输入商品数量
    scanf("%d", &n);
    // 输入天数
    scanf("%d", &days);

    // 输入每种商品的最大数目
    int *numbers = (int *)malloc(n * sizeof(int));
    for (int i = 0; i < n; i++) {
        scanf("%d", &numbers[i]);
    }

    // 初始化答案变量
    int ans = 0;

    // 循环n次，输入每种商品在days天中的价格变化
    for (int i = 0; i < n; i++) {
        int *prices = (int *)malloc(days * sizeof(int));
        for (int j = 0; j < days; j++) {
            scanf("%d", &prices[j]);
        }

        // 计算每种商品的总利润并累加到ans
        ans += maxProfit(prices, days) * numbers[i];
        free(prices);
    }

    printf("%d\n", ans);
    free(numbers);

    return 0;
}

Node JavaScript

const readline = require('readline');

// 计算某个特定商品能取得的最大利润的函数
// 动态规划实现，与LeetCode 122类似
function maxProfit(prices, days) {
    // 两种状态均表示第i天已经能够得到的最大利润
    // dp[0]: 持有股票
    // dp[1]: 没持有股票
    let dp = [-prices[0], 0];

    for (let i = 1; i < days; i++) {
        const p = prices[i];
        dp = [
            Math.max(dp[0], dp[1] - p),  // 今天持有 = max(之前持有, 今天买入)
            Math.max(dp[1], dp[0] + p)   // 今天没持有 = max(之前没持有, 今天卖出)
        ];
    }
    return dp[1];
}

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

let input = [];
rl.on('line', line => {
    input.push(line.trim());
}).on('close', () => {
    // 输入处理
    const n = parseInt(input[0]);
    const days = parseInt(input[1]);
    const numbers = input[2].split(' ').map(Number);
    
    let ans = 0;

    for (let i = 0; i < n; i++) {
        const prices = input[i + 3].split(' ').map(Number);
        ans += maxProfit(prices, days) * numbers[i];
    }

    console.log(ans);
});

Go

package main

import (
    "bufio"
    "fmt"
    "os"
    "strconv"
    "strings"
)

// 计算某个特定商品能取得的最大利润的函数
// 动态规划实现，与LeetCode 122类似
func maxProfit(prices []int, days int) int {
    // 两种状态均表示第i天已经能够得到的最大利润
    // dp[0]: 持有股票
    // dp[1]: 没持有股票
    dp := []int{-prices[0], 0}

    for i := 1; i < days; i++ {
        p := prices[i]
        dp = []int{
            max(dp[0], dp[1]-p), // 今天持有 = max(之前持有, 今天买入)
            max(dp[1], dp[0]+p), // 今天没持有 = max(之前没持有, 今天卖出)
        }
    }
    return dp[1]
}

// 获取最大值的辅助函数
func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

func main() {
    scanner := bufio.NewScanner(os.Stdin)

    // 输入商品数量
    scanner.Scan()
    n, _ := strconv.Atoi(scanner.Text())

    // 输入天数
    scanner.Scan()
    days, _ := strconv.Atoi(scanner.Text())

    // 输入每种商品的最大数目
    scanner.Scan()
    numbersStr := strings.Split(scanner.Text(), " ")
    numbers := make([]int, n)
    for i := 0; i < n; i++ {
        numbers[i], _ = strconv.Atoi(numbersStr[i])
    }

    ans := 0
    for i := 0; i < n; i++ {
        // 输入每种商品的价格变化
        scanner.Scan()
        pricesStr := strings.Split(scanner.Text(), " ")
        prices := make([]int, days)
        for j := 0; j < days; j++ {
            prices[j], _ = strconv.Atoi(pricesStr[j])
        }

        // 计算每种商品的总利润并累加到ans
        ans += maxProfit(prices, days) * numbers[i]
    }

    fmt.Println(ans)
}

时空复杂度

时间复杂度：O(NM)。需要循环N种商品，每次都要遍历M天来计算最大利润。

空间复杂度：O(1)。滚动数组仅需O(1)的空间。

华为OD算法/大厂面试高频题算法练习冲刺训练

华子OD算法/大厂面试高频题算法冲刺训练目前开始常态化报名！目前已服务1000+同学成功上岸！
课程讲师为全网200w+粉丝编程博主@吴师兄学算法 以及小红书头部编程博主@闭着眼睛学数理化
90+天陪伴式学习，100+直播课时，300+动画图解视频，500+LeetCode经典题，500+华为OD真题/大厂真题，还有简历修改、模拟面试、陪伴小群、资深HR对接将为你解锁
可上全网独家的欧弟OJ系统练习华子OD、大厂真题
可查看链接OD真题汇总(持续更新)
绿色聊天软件戳 od1441或了解更多

亚马逊云科技技术品牌专区

更多推荐

一次 API 调用搞定时序预测：时序大模型 TimechoAI 使用与能力全解析

亚马逊云科技技术品牌专区

智能软件工程AI4SE（十六）——需求工程工具Jira

亚马逊云科技技术品牌专区

AI Agent 面试题 353：A2A协议的服务发现和注册机制详解

A2A 协议是 AI Agent 技术体系中的重要组成部分。简单来说，它涉及到 Agent 如何在工具使用与函数调用层面实现智能化的行为和决策。在实际应用中，A2A 协议的核心目标是让 Agent 能够更加高效、准确地完成特定任务。这需要我们深入理解其底层原理和实现机制。从学术角度来看，A2A 协议的研究可以追溯到人工智能的早期阶段。早在 1950 年代，Alan Turing 就提出了

亚马逊云科技技术品牌专区

所有评论(0)

查看更多评论

闭着眼睛学算法

@weixin_48157259

已为社区贡献4条内容

华为OD笔试之【DP/贪心】双机位A-贪心的商人【Py/Java/C++/C/JS/Go六种语言OD独家双机位A卷真题】【欧弟算法】全网注释最详细分类最全的华子OD真题题解

闭着眼睛学算法

文章目录

相关推荐阅读

题目描述与示例

题目描述

输入描述

输出描述

说明

示例

输入

输出

解题思路

代码

解法一：贪心

Python

Java

C++

C

Node JavaScript

Go

时空复杂度

解法二：dp（吴师兄股票问题模板写法）

Python

Java

C++

C

Node JavaScript

Go

时空复杂度

*解法三：dp（许老师滚动dp数组写法）

Python

Java

C++

C

Node JavaScript

Go

时空复杂度

华为OD算法/大厂面试高频题算法练习冲刺训练

所有评论(0)

温馨提示：您尚未绑定手机号

闭着眼睛学算法