首页 > 试题广场 >

买卖股票的最好时机(一)

[编程题]买卖股票的最好时机(一)
  • 热度指数：174230 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
假设你有一个数组prices，长度为n，其中prices[i]是股票在第i天的价格，请根据这个价格数组，返回买卖股票能获得的最大收益
1.你可以买入一次股票和卖出一次股票，并非每天都可以买入或卖出一次，总共只能买入和卖出一次，且买入必须在卖出的前面的某一天
2.如果不能获取到任何利润，请返回0
3.假设买入卖出均无手续费

数据范围：
要求：空间复杂度 ，时间复杂度
示例1

输入

[8,9,2,5,4,7,1]

输出

5

说明

在第3天(股票价格 = 2)的时候买入，在第6天(股票价格 = 7)的时候卖出，最大利润 = 7-2 = 5 ，不能选择在第2天买入，第3天卖出，这样就亏损7了；同时，你也不能在买入前卖出股票。
示例2

输入

[2,4,1]

输出

2
示例3

输入

[3,2,1]

输出

0
算法知识视频讲解
查看答案及解析
添加回答
Javascript
觉醒乎头像 觉醒乎
/**
  * 
  * @param prices int整型一维数组 
  * @return int整型
  */
function maxProfit( prices ) {
    // write code here
    //循环实现。
    /**
    let len = prices.length;
    let max_profit = 0;
    for(let i=0;i<len;i++){
        for(let j=i;j<len;j++){
            let diff = prices[j] - prices[i];
            max_profit = max_profit < diff ? diff : max_profit;
        }
    }
    return max_profit;
    */
// 擂台法
    //思路 1.使用 minPrice 存储当前最低价格，遍历时依次对比更新
    //     2.使用 profit 存储当前最大利润，当前价格减去最低价格得到当前的最大利润 
    // profit = prices[i] - minPrice，动态得到最大利润
    let minProfit = prices[0];//先设置最小值为第一个数
    let profit = 0;
    for(var i = 0;i< prices.length;i++){
        minProfit = Math.min(minProfit,prices[i]);
        
        profit = Math.max(profit,prices[i]-minProfit);//计算最大利润。
        
    }
    return profit;
}
module.exports = {
    maxProfit : maxProfit
};

发表于 2021-11-15 00:16:21 回复(0)
DFT菜鸟头像 DFT菜鸟 
#
# 
# @param prices int整型一维数组 
# @return int整型
#
class Solution:
    def maxProfit(self , prices ):
        # write code here
        lst = []
        if len(prices) == 0 or len(prices)==1 :
            return 0
        for i in range (len(prices)-1):
            for j in range(i+1,len(prices)):
                
                x = prices[j]-prices[i]
                lst.append(x)
        if max(lst)<=0:
            return 0
        else:
            return max(lst)



#
# 
# @param prices int整型一维数组 
# @return int整型
#
class Solution:
    def maxProfit(self , prices ):
        # write code here
        lst = []
        if len(prices) == 0&nbs***bsp;len(prices)==1 :
            return 0
        for i in range (len(prices)-1):
            for j in range(i+1,len(prices)):
                
                x = prices[j]-prices[i]
                lst.append(x)
        if max(lst)<=0:
            return 0
        else:
            return max(lst)
            

编辑于 2021-06-10 10:44:21 回复(0)
羊羊羊~头像 羊羊羊~ 
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int min_price = prices[0]; // 最低价
        int max_money = 0; // 最高利润
        for (int i = 0; i < prices.size(); ++i) {
            min_price = min(min_price, prices[i]);
            max_money = max(prices[i] - min_price, max_money);
        }
        return max_money;
    }
};

发表于 2021-06-06 21:06:12 回复(0)
Java
真让人难为情头像 真让人难为情 
import java.util.*;


public class Solution {
    /**
     * f(x) = prices[x] - min(price[0 ~ x-1])
     * f(1) = max(prices[1] - prices[0], 0);
     * f(0) = 0;
     * @param prices int整型一维数组 
     * @return int整型
     */
    public int maxProfit (int[] prices) {
        // write code here
        if(prices==null||prices.length <= 1){
            return 0;
        }
        
        int[] f = new int[prices.length];
        f[0] = 0;
        f[1] = Math.max(prices[1] - prices[0],0);
        int max = Math.max(f[0],f[1]);
        int min = Math.min(prices[1] , prices[0]);
        
        for(int x = 2; x < prices.length; x++){
            min = Math.min(min,prices[x]);
            max = Math.max(max,f[x] = prices[x] - min);
        }
        return max;
    }
}

发表于 2020-09-19 23:02:44 回复(0)
黄色变白色头像 黄色变白色 
class Solution {
public:
    int maxProfit(vector<int> &prices) {
        int len = prices.size();
        int tempIncome = 0;
        int maxIncome = 0;
        for(int i=1;i<len;i++) {
            if(tempIncome < 0)
                tempIncome = prices[i] - prices[i-1];
            else
                tempIncome = tempIncome + prices[i] - prices[i-1];
            if(tempIncome > maxIncome)
                maxIncome = tempIncome;
        }
        return maxIncome;
    }
};

发表于 2020-09-04 14:11:20 回复(0)
|讨厌鬼|头像 |讨厌鬼| 
public class Solution {
    public int maxProfit(int[] prices) {
        if (prices.length<1) return 0;
        int sum = 0, min = prices[0];
        for (int i=0; i<prices.length; i++){
            if (prices[i] < min) min = prices[i];
            else if (prices[i] > min) sum = Math.max(sum, prices[i] - min);
        }
        return sum;
    }
}

发表于 2019-07-23 20:11:37 回复(0)
Java
阿拉要洗澡头像 阿拉要洗澡
public class Solution {
    public int maxProfit(int[] prices) {
        if(prices.length==0){
            return 0;
        }
        
        int max=0;
        int min=Integer.MAX_VALUE;
        
        for(int i=0;i<prices.length;i++){
            
            min=Math.min(min, prices[i]);
            max=Math.max(max,prices[i]-min);
        }
        
        return max;
    }
}
发表于 2017-08-07 11:15:02 回复(0)
C/C++
nbgao头像 nbgao 
class Solution {
public:
    int maxProfit(vector<int> &prices) {
        int MaxProfit = 0,Min = prices[0];
        for(int i=1;i<prices.size();i++)
        {
        	if(prices[i]>Min)
        		MaxProfit = max(MaxProfit,prices[i]-Min);
        	else
        		Min = prices[i];
		}
		return MaxProfit;
    }
};

发表于 2017-07-25 01:06:23 回复(0)
JacobGo！头像 JacobGo！ 
/*
	 * Runtime: Runtime: 1 ms.Your runtime beats 86.61 % of java submissions
	 */
	public int maxProfit(int[] prices) {
		if(prices==null||prices.length<2)
			return 0;
		int minNum=prices[0],maxPro=0;
		for(int i=1;i<prices.length;i++){
			if(prices[i]<minNum)
				minNum=prices[i];
			else if(prices[i]>minNum)
				maxPro=Math.max(maxPro, prices[i]-minNum);
		}
		
		return maxPro;
	}

发表于 2017-07-15 09:12:35 回复(0)
C/C++
秋日思宇头像 秋日思宇
class Solution {
public:
    int maxProfit(vector<int> &prices) {
     if(prices.empty())
        return 0;
    int len = prices.size();
    int minPirce = prices[0];
    int maxPro = 0;
    for(int i = 0;i<len;i++)
    {
        minPirce = minPirce > prices[i] ? prices[i] : minPirce;
        maxPro = maxPro > prices[i] - minPirce ? maxPro : prices[i] - minPirce;
    }
    return maxPro;
    }
};
made by CaryZhou
仅供参考
发表于 2017-05-22 14:10:48 回复(0)
Java
放学后我不走~头像 放学后我不走~ 
public class Solution {
    public int maxProfit(int[] prices) {
        if(prices==null || prices.length<1)
                    return 0;    
      int maxProfit=0;    
      int minPrice=prices[0];    
      for(int i=1;i<prices.length;i++){   
      if(prices[i]-minPrice>maxProfit) 
                        maxProfit = prices[i]-minPrice;   
      else if(prices[i]<minPrice)    
      minPrice = prices[i];    
      }    
      return maxProfit;
    }
}

编辑于 2018-08-31 12:15:32 回复(0)
Bapee头像 Bapee
保存每个最小值点，更新维护该值后面较大值和最小值的差即可 
public class Solution {
    public int maxProfit(int[] prices) {
        if(prices == null || prices.length==0)
            return 0;
        int min = prices[0];
        int res = 0;
        for(int i =1;i<prices.length;i++){
            if(prices[i]>min)
                res = res>prices[i]-min?res:prices[i]-min;
            else
                min = prices[i];
        }
        return res;
    }
}

发表于 2017-11-23 03:21:55 回复(0)
W.sl头像 W.sl 
public class Solution {
    public int maxProfit(int[] prices) {
        if(prices==null||prices.length==0){
            return 0;
        }
        int max=0;
        int min=prices[0];
        for(int i=0;i<prices.length;i++){
            min = Math.min(min,prices[i]);
            max=Math.max(max,prices[i]-min);
        }
        return max;
    }
}

发表于 2016-11-16 17:00:44 回复(3)
为你扣下F键头像 为你扣下F键 
//贪心算法，从左往右遍历向量，遇到当前最小值，则保存，
//如果不是最小值，则计算它到最小值的距离，保存为最大利润
class Solution {
public:
    int maxProfit(vector<int> &prices) {
        int min_num = prices[0];
        int max_profit = 0;
        for(int i=1; i<prices.size(); ++i){
            if(prices[i]<min_num)
                min_num = prices[i];//更新最小值
            else
                max_profit = max(max_profit, prices[i]-min_num);
        }
        return max_profit;
    }
};

发表于 2018-08-16 21:45:12 回复(4)
C/C++
永恒之蓝。头像 永恒之蓝。

思路如下:
我们需要可以遍历这个数组,在遍历的同时维护一个变量min来记录当前为止,历史中的最小的价格(作为买入价格),之后我们用当前的价格减去这个买入的价格,就可以得到可以赚的价格,因此我们再来维护一个max来记录最高可赚的价格,遍历完成之后的max就是最终的结果,
代码如下,仅供参考:

int maxProfit(int *prices,int pricesSize){
    if(prices == NULL || pricesSize == 0)
        return 0;

    int min = prices[0];
    int max = -1;

    for(int i = 0;i < pricesSize; ++i){
        //min用来维护历史的最小值
        if(min > prices[i])
            min = prices[i];
        //max用来管理最大的利润
        if(max < prices[i] - min)
            max = prices[i] - min;
    }
    return max;
}
发表于 2020-12-31 00:36:37 回复(1)
Java
AriesLi头像 AriesLi 
class Solution {
    /**
     *  找最小值和此后的最大值是最简单的
     *  为了方便理解后面系列题目，使用转移方程
     *  假设第i天持有股票的收益是 f(i,1), 未持有是f(i,0)
     *  f(i,0) = max(f(i-1, 0), f(i-1, 1)+prices[i])
     *  f(i,1) = max(f(i-1, 1), f(i-1, 0)-prices[i])
     *  对于f(i,1)因为只能买一次所以f(i-1,0)=0
     *  f(i,1) = max(f(i-1, 1), 0-prices[i])
     */
    public int maxProfit(int[] prices) {
        if(prices.length<2) return 0;
        int i0=0,i1=-prices[0];
        for(int i = 1; i < prices.length; i++){
            i0 = Math.max(i0, i1+prices[i]);
            i1 = Math.max(i1, -prices[i]);
        }
        return i0;
    }
}

发表于 2020-01-08 15:10:33 回复(1)
Python
wengJJ头像 wengJJ
Python
一旦利润变为负，则证明出现新的最低价格
迭代替换 最低价格min_p与最大利润max_m 即可解题 
#
# 
# @param prices int整型一维数组 
# @return int整型
#
class Solution:
    def maxProfit(self , prices ):
        # write code here
        if not prices&nbs***bsp;prices==1:
            return 0
        min_p=prices[0]
        money=0
        max_m=0
        for p in prices:
            money = p-min_p
            if money<0:
                min_p=p
            if money>max_m:
                max_m=money
        return max_money


发表于 2021-04-20 12:51:20 回复(0)
C/C++
QT菜鸡弟弟头像 QT菜鸡弟弟 
class Solution {
public:
    int maxProfit(vector<int> &prices) {
        int size = prices.size();
        if(size<=0) return 0;
        int max = 0;
        int gain = 0;
        for(int i=0;i<size;i++)
            for(int j=i;j<size;j++)
            {
                gain = prices[j]-prices[i];  //记录长和跌的情况
                if(max<gain)max = gain;  //与所有长幅相比，最后为最大收益
            }
        return max;
    }
};

发表于 2019-09-18 16:12:13 回复(1)
C++
QNBZ头像 QNBZ 
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int profit=0;
        for(int i=1;i<prices.size();i++)
        {
            profit=max(profit,prices[i]-prices[i-1]);
            prices[i]=min(prices[i-1],prices[i]);
        }
        return profit;
    }
};

发表于 2022-01-06 09:07:50 回复(0)
ChandlerMing头像 ChandlerMing 
class Solution {
public:
    /**
     * 
     * @param prices int整型vector 
     * @return int整型
     */
    int maxProfit(vector<int>& prices) {
        int size = prices.size(),
            max = INT_MIN,
            dp = 0;
        
        if(size<2){
            return dp;
        }
        for(int i=0;i<size-1;i++){
            dp = dp + prices[i+1] - prices[i] > 0 ? dp + prices[i+1] - prices[i] : 0;
            max = dp > max ? dp : max;
        }
        
        return max;
    }
};

发表于 2020-12-25 22:03:52 回复(0)
提交观点

问题信息

贪心 动态规划
难度：
395条回答 30143浏览

热门推荐

通过挑战的用户

查看代码

相关试题

买卖股票的最好时机(一)

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号