首页 » C++ » Leetcode#121. Best Time to Buy and Sell Stock(股票一次买卖的最佳时期-

Leetcode#121. Best Time to Buy and Sell Stock(股票一次买卖的最佳时期-

原文 http://blog.csdn.net/xunalove/article/details/79173830

2018-01-27 02:00:52阅读(481)

题目

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)

题意

告诉你,有一个数组,数组中的第i个元素代表第i天的股票的价格,现在要求你只能进行一次买卖的交易且必须先买后卖,求出所给数组中买卖交易获得的最大的利润。

题解

普通的解法:找出数组中b-a的最大值(a在前为买,b在后为卖),枚举法双层循环。

python语言
class Solution(object):
    def maxProfit(self, prices):
        """
        :type prices: List[int]
        :rtype: int
        """
        max =-1
        for buy in range(0, len(prices)):
            for sell in range(buy+1, len(prices)):
                if prices[sell]-prices[buy]>max:
                    max = prices[sell] - prices[buy]
        if max<0:
            return 0
        else:
            return max

超时。。。。。。。。。。。。肿么办?
优化,找出相对最小值,用当前的值-相对最小值与利润相比较,取最大。

python语言
#python语言
class Solution(object):
    def maxProfit(self, prices):
        """
        :type prices: List[int]
        :rtype: int
        """
        if len(prices)==0:
            return 0
        min_buy = prices[0]
        profit = -1
        for index in range(0, len(prices)):
            if min_buy > prices[index]:
                min_buy = prices[index]
            else:
                if prices[index]-min_buy>profit:
                    profit = prices[index]-min_buy
        return profit
C++语言
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        if(prices.size()==0)
            return 0;
        int min_buy=prices[0];
        int profit=-1;
        for(int i=0; i<prices.size(); i++)
        {
            if(min_buy > prices[i])
                min_buy = prices[i];
            else
            {
                if(prices[i] - min_buy > profit)
                    profit = prices[i] - min_buy;
            }
        }
        return profit;
    }
};

最新发布

CentOS专题

关于本站

5ibc.net旗下博客站精品博文小部分原创、大部分从互联网收集整理。尊重作者版权、传播精品博文,让更多编程爱好者知晓!

小提示

按 Ctrl+D 键,
把本文加入收藏夹