华为OD机试真题【最大利润】

1、题目描述

【最大利润】
商人经营一家店铺，有number种商品，由于仓库限制每件商品的最大持有数量是item[index]
每种商品的价格是item-price[item_index][day]
通过对商品的买进和卖出获取利润
请给出商人在days天内能获取的最大的利润
注：同一件商品可以反复买进和卖出

2、解题思路

该题是买卖股票最佳时机的改编题，可用贪心算法和动态规划解题。这题运用贪心算法思想解题，首先将最大利润设置为0。然后遍历Q每件商品，计算利润。
●遍历每天的价格，计算该商品每天的利润当天价格 减 前一天价格的差值，如果差值为负数,则取0。
●将每天的利润累加，得到该商品总利润。
●计算该商品的最大利润，商品利润*仓库限制的最大持有数量。
●将商品最大利润累加到总利润。

3、参考代码

import java.util.Scanner;/*** @Author * @Date 2023/4/26 23:10*/
public class 最大利润 {public static void main(String[] args) {Scanner in = new Scanner(System.in);while (in.hasNext()) {int number = in.nextInt();int days = in.nextInt();int[] item = new int[number];int[][] prices = new int[number][days];  // 每件商品每天的价格for (int i = 0; i < number; i++) {item[i] = in.nextInt();}for (int i = 0; i < number; i++) {for (int j = 0; j < days; j++) {prices[i][j] = in.nextInt();}}// 最大利润int res = 0;// 遍历每件商品，计算利润for (int i = 0; i < number; i++) {int maxPrice = 0;// 遍历每天的价格，计算该商品每天的利润for (int j = 1; j < days; j++) {maxPrice += Math.max(0, prices[i][j] - prices[i][j - 1]);}// 将商品利润累计到总利润中res += maxPrice * item[i];}System.out.println(res);}}
}

4、相似题目

（1）买卖股票的最佳时机 II

	public int maxProfit(int[] prices) {int ans = 0;int n = prices.length;for (int i = 1; i < n; ++i) {ans += Math.max(0, prices[i] - prices[i - 1]);}return ans;}