【贪心】2024E-贪心的商人

题目描述与示例

题目描述

商人经营一家店铺，有 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；

示例

输入

3
3
4 5 6
1 2 3
4 3 2
1 5 3

输出

32

1 2 3 4 1 3 5

1+1+1（局部的最优解） = 3 (连续递增子数组的全局的最优解)

2+2 （局部的最优解）= 4 （连续递增子数组的全局最优解）

解题思路

注意，本题的核心逻辑和LeetCode 122、买卖股票的最佳时机 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

# 题目：2024E-贪心的商人
# 分值：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

# 题目：2024E-贪心的商人
# 分值：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

# 题目：2024E-贪心的商人
# 分值：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)的空间。