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

你的名字 2023-10-10 18:26 84阅读 0赞

#### 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][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;
        }

[II]: https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-ii/