java – 最大单一销售利润算法的最优解决方案

发布时间：2020-12-15 02:04:17 所属栏目：Java 来源：网络整理

导读：输入数组是： A[0] = 23171 A[1] = 21015 A[2] = 21123A[3] = 21366 A[4] = 21013 A[5] = 21367 使命是找到最大的利润.例如[3] – A [2] = 243 我的代码是： class Solution { int profit = 0; public int solution(int[] A) { for (int i = 0;i A.length; i

输入数组是：

A[0] = 23171 
A[1] = 21015 
A[2] = 21123
A[3] = 21366 
A[4] = 21013 
A[5] = 21367

使命是找到最大的利润.例如[3] – A [2] = 243
我的代码是：

class Solution {
    int profit = 0;
    public int solution(int[] A) {
         for (int i = 0;i < A.length; i++){
            for (int j = i + 1; j < A.length; j++){
                if(A[j] - A[i] > profit)
                    profit = A[j] - A[i];
            }
         }
         return profit;
   }
}

结果假设是365,但它会在更大的输入上爆炸.
该代码的时间复杂度为O(N2),但可能与O(N)有关.我无法真正看到如何避免在这里筑巢……任何正确方向的指针都会受到赞赏.

解决方法

我认为大多数人都错了.这篇文章中的问题是最大的单一销售利润问题,这是一个典型的面试问题.

最佳解决方案：

public int dynamicProgrammingSingleSellProfit(int[] arr) {
        if(arr.length == 0) {
            return 0;
        }
        int profit = 0;
        int cheapest = arr[0];

        for (int i = 0; i < arr.length; i++) {

            cheapest = Math.min(cheapest,arr[i]);
            profit = Math.max(profit,arr[i] - cheapest);

        }
        return profit;
    }

它具有O(n)时间和O(1)空间复杂度.

如果你检查原始问题,op正在寻找利润,因为我们不能及时旅行(你)不能只比较数组中的最小值和最大值.

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!