首页 > 试题广场 >

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

[编程题]买卖股票的最好时机(二)
  • 热度指数：42046 时间限制：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]

输出

7

说明

在第1天(股票价格=8)买入，第2天(股票价格=9)卖出，获利9-8=1
在第3天(股票价格=2)买入，第4天(股票价格=5)卖出，获利5-2=3
在第5天(股票价格=4)买入，第6天(股票价格=7)卖出，获利7-4=3
总获利1+3+3=7，返回7
示例2

输入

[5,4,3,2,1]

输出

0

说明

由于每天股票都在跌，因此不进行任何交易最优。最大收益为0。
示例3

输入

[1,2,3,4,5]

输出

4

说明

第一天买进，最后一天卖出最优。中间的当天买进当天卖出不影响最终结果。最大收益为4。

备注:
总天数不大于200000。保证股票每一天的价格在[1,100]范围内。
算法知识视频讲解
添加回答
Java
w浩头像 w浩 
import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 计算最大收益
     * @param prices int整型一维数组 股票每一天的价格
     * @return int整型
     */
    public int maxProfit (int[] prices) {
        // write code here
        int profits = 0;
        int len = prices.length;
        for(int i =1;i<len;i++){
            if(prices[i]>prices[i-1]){
                profits+=prices[i]-prices[i-1]; //逢高卖出
            }
        }
        return profits;
    }
}

发表于 2021-07-15 23:10:22 回复(0)
木析头像 木析 
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 计算最大收益
     * @param prices int整型vector 股票每一天的价格
     * @return int整型
     */
    int maxProfit(vector<int>& prices) {
        int res=0;
        for(int i=1;i<prices.size();i++) {
            if(prices[i]>prices[i-1]) {
                res+=prices[i]-prices[i-1];
            }
        }
        return res;
    }
};

发表于 2021-03-20 21:51:33 回复(0)
Newman1997头像 Newman1997
只要涨价，我就先买后卖，将差价加入结果中。
只要降价，就按兵不动，更新当前位置。 
function maxProfit( prices ) {
    let curr=prices[0]
    let res=0
    for(let i=1;i<prices.length;i++){
        if(prices[i]>curr){
            res+=prices[i]-curr
            curr=prices[i]
        }else{
            curr=prices[i]
        }
    }
    return res
}


发表于 2021-03-14 23:03:33 回复(0)
板爷头像 板爷 
import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 计算最大收益
     * @param prices int整型一维数组 股票每一天的价格
     * @return int整型
     */
    public int maxProfit (int[] prices) {
        //持有股票1和不持有股票0两种状态，第0天和第1，2，3...第prices.length天
        int[][] dp = new int[2][prices.length + 1];

        //第0天未持有股票，收益为0
        dp[0][0] = 0;
        //第0天持有股票，不存在，收益为负无穷
        dp[1][0] = Integer.MIN_VALUE;

        for (int i = 1; i <= prices.length; i++) {
            //第i天未持有股票，两个可能：
            //1.在前面i-1天都持有，第i天卖掉了，卖掉价值增加。dp[1][i - 1] + prices[i - 1]
            //2.到当前为止都为未持有，维持第i-1天的结果。dp[0][i - 1]
            dp[0][i] = Math.max(dp[0][i - 1], dp[1][i - 1] + prices[i - 1]);
            //第i天持有股票，两个可能：
            //1.在前面i-1天都未持有，第i天买入了，总价值减少。dp[0][i - 1] - prices[i - 1]
            //2.到当前为止都为持有，维持第i-1天的结果。dp[1][i - 1]
            dp[1][i] = Math.max(dp[1][i - 1], dp[0][i - 1] - prices[i - 1]);
        }

        //获取最后一天卖掉的最大值
        return dp[0][prices.length];
    }
}

编辑于 2021-04-19 15:31:09 回复(0)
Java
菲尼克斯弗兰克头像 菲尼克斯弗兰克
投机取巧的方法 只要涨我就卖，当天我可以卖了再买 跟真实的股市不一样 
public class Solution {
    public int maxProfit (int[] prices) {
        int profit = 0;
        for (int i = 1; i < prices.length; i++) {
            if (prices[i] > prices[i-1])
                profit += prices[i] - prices[i-1];
        }
        return profit;
    }
}
发表于 2021-08-06 11:59:00 回复(2)
RmondJone头像 RmondJone 
import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 计算最大收益
     * @param prices int整型一维数组 股票每一天的价格
     * @return int整型
     */
    public int maxProfit (int[] prices) {
        // write code here
        int profit=0;
        for(int i=1;i<prices.length;i++){
           if(prices[i]>prices[i-1]){
             profit+=prices[i]-prices[i-1];  
           }
        }
        return profit;
    }
}

发表于 2021-01-21 17:57:38 回复(0)
C
算帝头像 算帝 
int maxProfit(int* prices, int n ) {
    int sum = 0;
    int i = 0;
    if(n < 2) return 0;
    while(i < n-1) {    //将股票价格画成折线图，计算上升沿的总长度
        if(prices[i] < prices[i+1]) {
            sum += prices[i+1] - prices[i];
        }
        i++;
    }
    return sum;
}
发表于 2023-01-08 23:25:54 回复(0)
C++
牛客336721596号头像 牛客336721596号
股市有风险，投资需谨慎
发表于 2021-11-20 16:49:14 回复(0)
花落梦里头像 花落梦里 
    public int maxProfit (int[] prices) {
        int n=prices.length,profit=0;
        for(int i=1;i<n;i++){
            if(prices[i]>prices[i-1])
                profit+=prices[i]-prices[i-1];
        }
        return profit;
    }

发表于 2021-02-05 16:22:29 回复(1)
起个昵称可真难头像 起个昵称可真难 
int maxProfit(vector<int>& prices) {
        //完成无限次的交易
        int size=prices.size();
        vector<vector<int>> dp(size,vector<int>(2,0));//1=持有 0=未持有
        dp[0][0]=0;
        dp[0][1]=-prices[0];
        for(int i=1;i<size;++i){
            dp[i][0]=std::max(dp[i-1][0],dp[i-1][1]+prices[i]);
            dp[i][1]=std::max(dp[i-1][1],dp[i-1][0]-prices[i]);
        }
        return dp[size-1][0];
    }

发表于 2020-09-19 22:26:50 回复(0)
JavaScript Node
想吃火锅的猴子在刷题头像 想吃火锅的猴子在刷题 
function maxProfit( prices ) {
    // write code here
    let profit = 0
    for(let i = 1; i < prices.length; i++) {
        if(prices[i] > prices[i - 1]) {
            profit += prices[i] - prices[i - 1]
        }
    }
    return profit
}

发表于 2023-12-01 10:38:38 回复(0)
Python3
talv头像 talv
我怎么觉得这一题比第一部分还要简单 
class Solution:
    def maxProfit(self , prices: List[int]) -> int:
        if len(prices)>= 1:
            a = [0]*len(prices)
            for i in range(1,len(prices)):
                a[i] = max(prices[i]-prices[i-1],0)
            return sum(a)
        else:
            return 0


发表于 2023-03-17 00:26:09 回复(0)
Python3
猫牛头像 猫牛 
需要毛的动态规划啊。直接遍历求解
class Solution:
    def maxProfit(self , prices: List[int]) -> int:
        # write code here
        n = len(prices)
        if n < 2:
            return 0
        
        res = 0
        i = 0
        while i < n-1:
            if prices[i+1] > prices[i]:
                res += prices[i+1] - prices[i]
                i += 1
            else:
                i += 1
        return res

发表于 2022-12-04 16:54:58 回复(0)
C++
Spectre_头像 Spectre_ 
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 计算最大收益
     * @param prices int整型vector 股票每一天的价格
     * @return int整型
     */
    int maxProfit(vector<int>& prices) {
        // 时间复杂度O(N)，空间复杂度O(N)
        if (prices.empty()) return 0;
        int dp[2][prices.size()];
        dp[0][0] = -prices[0], dp[1][0] = 0;
        for (int i = 1; i < prices.size(); ++i) {
            dp[0][i] = max(dp[0][i - 1], dp[1][i - 1] - prices[i]);
            dp[1][i] = max(dp[1][i - 1], dp[0][i - 1] + prices[i]);
        }
        return dp[1][prices.size() - 1];
    }
};

发表于 2022-11-09 11:19:37 回复(0)
Python 3
杰瑞扁头像 杰瑞扁 
class Solution:
    def maxProfit(self , prices: List[int]) -> int:
        n = len(prices)
        #dp[i][0]表示某一天不持股到该天为止的最大收益，dp[i][1]表示某天持股，到该天为止的最大收益
        dp = [[0] * 2 for i in range(n)]
        #第一天不持股，总收益为0
        dp[0][0] = 0
        #第一天持股，总收益为减去该天的股价
        dp[0][1] = -prices[0]
        #遍历后续每天，状态转移
        for i in range(1, n):
            # 第i天不持股有两种情况，第一种昨天就没有买股票，第二种昨天卖出了股票（这里一直保存最大收益，整个过程下来相当于只买了一次）
            dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i])
            # 第i天持股有两种情况，第一种昨天就持股，第二种昨天不持股，但是今天买入了（这里相当于寻找最最小值了）
            dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - prices[i])
        #最后一天不持股，到该天为止的最大收益
        return dp[n - 1][0]

发表于 2022-08-04 16:12:42 回复(2)
Python
黄滴伟头像 黄滴伟 
class Solution:
    def maxProfit(self , prices ):
        # write code here
        profit = 0
        for i in range(1, len(prices)):
            if prices[i] > prices[i-1]:
                profit += prices[i]-prices[i-1]
        return profit


发表于 2021-03-12 20:59:19 回复(0)
余生还长着呢头像 余生还长着呢 
import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 计算最大收益
     * @param prices int整型一维数组 股票每一天的价格
     * @return int整型
     */
    public int maxProfit (int[] prices) {
        // write code here
        // 状态定义dp[i][0]：表示在第i天不持有股票最大收益；dp[i][1]表示在第i天持有股票最大收益
        int dp[][] = new int[prices.length][2];
        // 初始化
        dp[0][0] = 0;
        dp[0][1] = -prices[0];
        // 遍历，状态转移
        for(int i = 1;i < prices.length;i++){
            dp[i][0] = Math.max(dp[i - 1][0],dp[i - 1][1] + prices[i]);
            dp[i][1] = Math.max(dp[i - 1][1],dp[i - 1][0] - prices[i]);
        }
        return dp[prices.length - 1][0];
    }
}

编辑于 2024-02-19 11:06:23 回复(0)
牛客2024007号头像 牛客2024007号 
import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 计算最大收益
     * @param prices int整型一维数组 股票每一天的价格
     * @return int整型
     */
    public int maxProfit (int[] prices) {
        // write code here
        int res = 0;
        for(int i = 1; i < prices.length; i++) {
            int gap = prices[i] - prices[i - 1];
            if(gap > 0) res += gap;
        }
        return res;
    }
}
不明白为啥是medium题，感觉股票一才应该是medium
编辑于 2024-01-10 16:41:14 回复(0)
Go
NightCruising头像 NightCruising

很容易想出这道题的状态转移方程

func MaxProfitBM81(prices []int) int {
    a, b := -prices[0], 0
    for i := 2; i <= len(prices); i++ {
        a, b = Max(a, b-prices[i-1]), Max(b, a+prices[i-1])
    }
    return b
}
编辑于 2024-01-08 14:39:46 回复(0)
萌新蒙蒙牛写代码不要懵头像 萌新蒙蒙牛写代码不要懵 
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        vector<int> dp(prices.size(), 0);
        for(int i=1;i<prices.size(); ++i){
            dp[i] = max(dp[i-1], dp[i-1] + prices[i] - prices[i-1]); 
        }
        return dp.back();
    }
};

发表于 2023-10-28 01:34:48 回复(0)
提交观点

问题信息

贪心 动态规划
难度：
99条回答 7208浏览

热门推荐

通过挑战的用户

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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