题目描述

Say you have an array for which the ith element is the price of a given stock on day i.

If you were only permitted to complete at most one transaction (ie, buy one and sell one share of the stock), design an algorithm to find the maximum profit.

Example 1:

Input: [7, 1, 5, 3, 6, 4]
Output: 5

max. difference = 6-1 = 5 (not 7-1 = 6, as selling price needs to be larger than buying price)

Example 2:

Input: [7, 6, 4, 3, 1]
Output: 0

In this case, no transaction is done, i.e. max profit = 0.

解法一

思路

这题是非常经典的题目了,其解法也是一个经典算法,即最大子数列问题

当然这题并不是标准的最大子数列问题,需要变换一下。我们想要寻找一个子数组,使得其收益最大,其实就可以等价为将此数组变换为由相邻元素的差组成的数组,来求这个新的数组的最大子数组。例如对于[7, 1, 5, 3, 6, 4],其相邻元素差组成的数组就是[-6, 4, -2, 3, -2],而其最大子数组就是[4, -2, 3],即其和为5

这里先不去考虑如何想出这个算法,先描述一下算法的工作过程。这里用到两个变量max_ending_here(初始值为0)记录以当前位置为子数组的最后一个元素得到的最大值(必须包含当前元素),max_so_far(初始值为0)记录直到当前位置得到的最大值(不必包含当前元素)。从前往后顺序遍历数组,对于每个元素:更新max_ending_here为加上当前元素值后的值,若新的max_ending_here小于0,则将max_ending_here置为0;更新max_so_farmax_ending_heremax_so_far中较大者。全部遍历完成后得到的max_so_far即为最终结果。

下面来说说这个算法里最难理解的部分。max_so_far的作用很简单,就是记录下max_ending_here所有取值中的最大值。而max_ending_here在每次加上当前元素值后,都会去考虑需不需要将“当前及以前的元素和”全部清零;可以想象,如果没有清零这个步骤的话,max_ending_here每次更新得到的值都是从第一个元素开始到当前元素的所有元素的和,这当然是错的。下面来考虑这个清零的时机是否恰当,“清零”换个理解方式就是:抛弃当前的子数组,而以其后一个元素作为新的子数组的第一个元素。那么有没有可能抛弃了太多子数组元素呢?即当前子数组的最后几个元素与与其后的元素可以组成更大的子数组吗?答案是否定的,因为如果有这样的情况出现,那么就不会出现“抛弃当前的子数组”的情况了。以[1, -4, 2, 3, -1]为例,如果将2和之前的子数组全部抛弃,那么由3开始的子数组最大也只能是3,而答案实际是[2, 3]5,这样算法就错了;仔细看看,算法遍历到2时,max_ending_here-1,确实应该抛弃,但别忘了算法是顺序便利的,实际上当算法遍历到-4时,max_ending_here已经为-3,这时就把子数组[1, -4]抛弃了,而当遍历到2时,当前的子数组就是[2]而不是[1, -4, 2]了。

Python

class Solution(object):
    def maxProfit(self, prices):
        """
        :type prices: List[int]
        :rtype: int
        """
        max_ending_here = 0
        max_so_far = 0
        for i in range(1, len(prices)):
            max_ending_here = max(0, max_ending_here + (prices[i] - prices[i - 1]))
            max_so_far = max(max_so_far, max_ending_here)
        return max_so_far

Java

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

C++

class Solution {
public:
    int maxProfit(vector<int> &prices) {
        int maxEndingHere = 0;
        int maxSoFar = 0;
        for (int i = 1; i < prices.size(); i++) {
            maxEndingHere = max(0, maxEndingHere + prices[i] - prices[i - 1]);
            maxSoFar = max(maxSoFar, maxEndingHere);
        }
        return maxSoFar;
    }
};