最大单笔销售利润算法的最优解决方案

Question

输入数组为：

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

任务是寻找最大利润。例如，A[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(N²)，但可以使用O(N)进行优化。我无法想象如何避免嵌套...任何指向正确方向的指针都将不胜感激。

- C.A

---

“large”输入的规模有多大？“blows up”是什么意思？ - Jon Skeet

你试图解决什么问题？两个条目之间最大的区别是什么？ - Adam Arold

它在输入值在10k-200k之间会崩溃。 - C.A

你正在寻找“最大值-最小值”的答案吗？如果是的话，最佳答案已经为您提供了。如果不是，请注意您的代码。 - Terry Zhao

可能是最大单次销售利润的重复问题。 - templatetypedef

Answer 1

你只需要从数组中获取最大值和最小值，然后将它们相减，因此在O（N）迭代中获取最小值和最大值。

class Solution {

    public int solution(int[] A) {

        int min = Integer.MAX_VALUE;
        int max = Integer.MIN_VALUE;

        for (int i = 0;i < A.length; i++){
            if(A[i] > max) max = A[i];
            if(A[i] < min) min = A[i];
        }

        return max - min;
    }
}

- RamonBoza

---

没有比这更好的纯解决方案，而且它的时间复杂度是O(n)! - Stefan

我读了这个问题，思考了一分钟，然后读了这个答案，我的下巴都掉了。点赞。 - Eric Wich

这个问题中没有空数组。 - C.A

在原始实现中，第二个索引j始终大于i -> for (int j = i + 1; j < A.length; j++)。但是这个实现没有强制执行这一点。 - nicopico

重读问题后，我意识到你理解错了。请检查我的答案。虽然你无法时空穿越，但在整个数组中查找最小值和最大值并不能找到收益。 - Adam Arold

Answer 2

我认为大多数人都理解错了。帖子中的问题是“最大单笔卖出利润问题”，这是一个典型的面试题。

最优解：

    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正在寻找利润，由于我们不能穿越时空 (尚未)，因此无法仅通过比较数组中的最小值和最大值来完成。

- Adam Arold

---

请查看我对其他答案的评论。 - Adam Arold

Adam，没错，这是一道面试测试题。你立刻就发现了。有什么地方可以让我了解这个吗？isa是什么意思？ - C.A

在谷歌上搜索“单次销售利润问题”。这里有一个详尽的Python解决方案（http://keithschwarz.com/interesting/code/?dir=single-sell-profit）。 - Adam Arold