首页 > 试题广场 >

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

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

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

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

1. 你可以多次买卖该只股票，但是再次购买前必须卖出之前的股票

2. 如果不能获取收益，请返回0

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

数据范围： $1 \le n \le 1 \times 10^5$ ， $1 \le prices[i] \le 10^4$

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

进阶：空间复杂度 $O(1)$ ，时间复杂度 $O(n)$

示例1

输入

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

输出

说明

在第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。

示例3

输入

[1,2,3,4,5]

输出

说明

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

备注:

总天数不大于200000。保证股票每一天的价格在[1,100]范围内。

算法知识视频讲解

Java

牛客455964074号

import java.util.*;


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

发表于 2023-10-11 19:18:54 回复(0)

Java

做则必成的勇气和信心

import java.util.*;


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

发表于 2023-04-12 20:48:23 回复(0)

Java

wpcAlex

import java.util.*;


public class Solution {
    public int maxProfit (int[] prices) {
        // write code here
        int ans = 0;
        for(int i = 1; i < prices.length; i++){
            ans += Math.max(prices[i] - prices[i - 1], 0);
        }
        return ans;
    }
}

发表于 2023-01-26 15:32:17 回复(0)

Java

不卷了，就测开了

推荐动态规划思路，一系列都使用动态规划

import java.util.*;


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

    }
}

发表于 2022-09-24 18:00:52 回复(0)

Java

俊朗的牛肉丸在求职

动态规划不是使用一个一维数组也可以吗，为啥官方动态规划要个二维数组。
import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 计算最大收益
     * @param prices int整型一维数组 股票每一天的价格
     * @return int整型
     */
    public int maxProfit (int[] prices) {
        // write code here
        int len = prices.length;
        //第i位置表示前i天收入的最大值
        int[] dp = new int[len +1];
        dp[0] = 0;
        dp[1] = 0;
        for(int i = 2;i<=len;i++){
            //第i天收入的最大值要么是前i-1天收入的最大值，要么第i天大涨，比第i-1 天的还要高，所以加上差值（可正可负）。。
            dp[i] = Math.max(dp[i-1],dp[i-1] + prices[i-1] - prices[i-2]);
        }
        return dp[len];
    }
}

发表于 2022-08-24 15:08:37 回复(0)

Java

牛客590756693号

import java.util.*;

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

发表于 2022-08-21 21:28:10 回复(0)

Java

KamTang

import java.util.*;

public class Solution {
    public int maxProfit (int[] prices) {
        if (prices == null || prices.length <= 1) {
            return 0;
        }
        // 收入
        int in = 0;
        for (int i = 0; i < prices.length - 1; i++) {
            in += Math.max(prices[i + 1] - prices[i], 0);
        }
        return in;
    }
}

发表于 2022-08-15 22:29:58 回复(0)

Java

yxjing

import java.util.*;


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

发表于 2022-08-15 14:38:07 回复(0)

Java

紫薇爸爸

import java.util.*;
public class Solution {
    public int maxProfit (int[] prices) {
        // write code here
        if(prices.length==0||prices.length==1) return 0;
        int len=prices.length;
        int[] profits = new int[len];
        for(int i=0;i<len-1;i++){
            profits[i]=prices[i+1]-prices[i];
        }
        int res=0;
        for(int i=0;i<len-1;i++){
            if(profits[i]>0){
                res+=profits[i];
            }
        }
        return res;
    }
}

图片说明

发表于 2022-04-02 17:04:52 回复(0)

Java

ieblYang

相邻两个后面的比前面的多就累加

import java.util.*;


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

发表于 2022-03-26 21:18:02 回复(0)

Java

老农爱编程

import java.util.*;
/**
    思路就是：从第一个开始找，如果找到下一个的值比该值大，那么就从下一个值再一直向后
            遍历，遍历到最峰值，就跳出循环，同时获取利润
*/

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 计算最大收益
     * @param prices int整型一维数组 股票每一天的价格
     * @return int整型
     */
    public int maxProfit (int[] prices) {
        // write code here
        int profit = 0 ;
        if(prices.length == 1){
            return 0;
        }
        for(int i = 0 ; i < prices.length ; i ++){
            if(i == prices.length - 1){
                break;
            }
            //如果当前值比后一个值小，
            if(prices[i] < prices[i + 1] ){
                //就从后一个值一直向后遍历，找到最顶峰的值，也就是找到不满足该值小于下一个值了
                int j = i + 1;
                while(j < prices.length - 1 && prices[j] < prices[j + 1]){
                    j ++ ; //继续
                }
                profit += prices[j] - prices[i]; // 跳出循环后，表示找到峰值，直接求利润
                i = j;//让下一次循环从该值的下一个值开始
            }
        }
        return profit;
    }
    
}

发表于 2022-01-21 12:43:09 回复(0)

Java

玄鉴

import java.util.*;


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

         return nohost>0?nohost:0;
    }
}

发表于 2022-01-01 17:43:55 回复(0)

Java

QinGL_ZYW

public int maxProfit (int[] prices) {
    int res = 0;
    for(int i = 1; i < prices.length; i++){
        if(prices[i] > prices[i-1]){
            res += prices[i] - prices[i-1];
        }
    }
    return res;
}

发表于 2021-11-04 10:01:20 回复(0)

Java

牛客48978033号

public int maxProfit (int[] prices) {
        // write code here
        if(prices==null || prices.length < 2) return 0;
        int profit = 0;
        int current = prices[0];
        for(int i = 1; i < prices.length; i++){
            if(current < prices[i]){
                profit += prices[i] - current;
            }
            current = prices[i];
        }
        
        return profit;
    }

发表于 2021-10-15 18:03:57 回复(0)

Java

已注销

public int maxProfit (int[] prices) {
        // write code here
        if (prices == null || prices.length <= 1) return 0;
        int maxProfit = 0;
        int minSoFar = prices[0];
        for (int i = 1; i <= prices.length - 1; i++) {
            if (prices[i] > minSoFar) {
                maxProfit += prices[i] - minSoFar;
                minSoFar = prices[i];
            } else {
                minSoFar = Math.min(minSoFar, prices[i]);
            }
        }
        return maxProfit;
    }

发表于 2021-08-26 21:14:47 回复(0)

Java

谁是谁的眼

public int maxProfit (int[] prices) {
// write code here
int res = 0;
int current = Integer.MAX_VALUE;

for(int i = 0; i < prices.length; i++){
if(prices[i] < current){
current = prices[i];
}else{
res += (prices[i] - current);
current = prices[i];
}
}

return res == Integer.MAX_VALUE ? 0 : res;
}

发表于 2021-08-22 21:38:37 回复(0)

提交观点

问题信息

贪心动态规划

难度：

29条回答 334收藏 9506浏览

通过挑战的用户

查看代码

s13

2022-12-30 00:00:26
黑子的脑残粉

2022-09-27 00:28:30
牛客35029...

2022-09-21 09:19:02
牛客93454...

2022-09-19 23:07:14
花酒水茶

2022-09-16 19:22:45

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

输入

输出

说明

输入

输出

说明

输入

输出

说明

备注:

问题信息

热门推荐

通过挑战的用户

相关试题