首页 > 试题广场 >

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

[编程题]买卖股票的最好时机(一)

热度指数：170237 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

假设你有一个数组prices，长度为n，其中prices[i]是股票在第i天的价格，请根据这个价格数组，返回买卖股票能获得的最大收益

1.你可以买入一次股票和卖出一次股票，并非每天都可以买入或卖出一次，总共只能买入和卖出一次，且买入必须在卖出的前面的某一天

2.如果不能获取到任何利润，请返回0

3.假设买入卖出均无手续费

数据范围： $0 \le n \le 10^5 , 0 \le val \le 10^4$

要求：空间复杂度 $O(1)$ ，时间复杂度 $O(n)$

示例1

输入

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

输出

说明

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

示例2

输入

[2,4,1]

输出

示例3

输入

[3,2,1]

输出

算法知识视频讲解

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菜鸟

#
# 
# @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

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！

/*
	 * 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

保存每个最小值点，更新维护该值后面较大值和最小值的差即可

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

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键

//贪心算法，从左往右遍历向量，遇到当前最小值，则保存，
//如果不是最小值，则计算它到最小值的距离，保存为最大利润
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

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

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菜鸡弟弟

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

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

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)