本文共 1996 字，大约阅读时间需要 6 分钟。

给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。

如果你最多只允许完成一笔交易（即买入和卖出一支股票），设计一个算法来计算你所能获取的最大利润。

注意你不能在买入股票前卖出股票。

示例 1:

输入: [7,1,5,3,6,4]

输出: 5

解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。

         注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格。

输入: [7,6,4,3,1]

输出: 0

解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。

扫描价格数组，维护一个最小值，当前元素-最小值>最大利润时，更新最大利润即可。

class Solution(object):    def maxProfit(self, prices):        """        :type prices: List[int]        :rtype: int        """        if not prices: # 列表为空是False            return 0        buy=prices[0] # 初始化第一个元素为最小元素        out=0        for i in range(1,len(prices)):            if prices[i]

结果为5，与题目一致

以下是Java版本：

题目大意：给一个数组prices[]，prices[i]代表股票在第i天的售价，求出只做一次交易(一次买入和卖出)能得到的最大收益。 

解题思路：只需要找出最大的差值即可，即 max(prices[j] – prices[i]) ，i < j。一次遍历即可，在遍历的时间用遍历low记录 prices[o….i] 中的最小值，就是当前为止的最低售价，时间复杂度为 O(n)。

public class Solution {    public int maxProfit(int[] prices) {        if (prices == null || prices.length < 1) {            return 0;        }        int min = prices[0];        int profit = 0;        // 第i天的价格可以看作是买入价也可以看作是卖出价        for (int i = 1; i < prices.length; i++) {            // 找到更低的买入价            if (min > prices[i]) {                // 更新买入价                min = prices[i];            }             // 当天的价格不低于买入价            else {                // 如果当天买出的价格比之前卖出的价格高                if (profit < prices[i] - min) {                    // 更新卖出价                    profit = prices[i] - min;                }             }        }        return profit;    }}

这道题求进行一次交易能得到的最大利润。如果用brute force的解法就是对每组交易都看一下利润，取其中最大的，总用有n*(n-1)/2个可能交易，所以复杂度是O(n^2)。

1.	public int maxProfit(int[] prices) {  2.	    if(prices==null || prices.length==0)  3.	        return 0;  4.	    int local = 0;  5.	    int global = 0;  6.	    for(int i=0;i

转载地址：http://nsuvi.baihongyu.com/