您将获得n天的n 个股票价格。输出您可以通过交易股票获得的最大利润。您每天最多只能交易一次：每天您可以选择买入一只股票，或者卖出一只股票（如果有的话），或者放弃当天的交易，什么也不做。
给定a = [1,2,10,9]，返回16
解释：
您可以在第 1 天和第 2 天买入，并在第 3 天和第 4 天卖出。
利润：-1-2+10+9 = 16
给定a = [9,5,9,10,5]，返回5
解释：
您可以在第 2 天买入并在第 4 天卖出。
利润：-5 + 10 = 5
困难的部分是您可以连续买入和/或卖出，这意味着一旦您拥有一只股票，您不必在购买另一只股票之前将其卖出。
我的想法是以下算法：
从最大价格开始，然后匹配输入数组中出现在该最大价格之前的最小价格。匹配后，从数组中删除这两个价格并不断重复此过程，直到找不到更多匹配为止。看起来这个算法是有效的，但它花费了O(n 2 )时间，这还不够快。
如何用更好的时间复杂度来解决这个问题，比如O(nlogn)？
algorithm ×1