首页 > 试题广场 >

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

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

热度指数：170213 时间限制：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]

输出

算法知识视频讲解

查看答案及解析

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], - prices[i]);
            dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] + prices[i]);
        }
        return dp[dp.length - 1][1];
    }
}

发表于 2023-10-11 19:30:09 回复(0)

Java

SUMMERENT

  public int maxProfit (int[] prices) {
        // write code here
        int min = Integer.MIN_VALUE;
        for (int i = 0; i < prices.length; i++) {
            for (int j = i + 1; j < prices.length; j++) {
                min = Math.max(min, prices[j] - prices[i]);
            }
        }
        if (min < 0) {
            min = 0;
        }
        return min;
}

发表于 2023-06-15 14:04:18 回复(0)

Java

牛明月

遍历每一个数，把这个数和之前遍历过的最小数相减得到的就是收益；

因此在每一轮中，需记录当前遇到过的最小值，以及已经计算过的最大值

    public int maxProfit (int[] prices) {
        int min = 10000;//记录当前轮之前遇到过的最小值
        int max = 0;//记录差值的最大值
        for(int i =0;i<prices.length;i++){
            max = Math.max(max,prices[i]-min);//更新差值
            min = Math.min(min,prices[i]);//更新最小值
        }
        return max;
    }

发表于 2023-04-14 16:55:52 回复(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];
        //0 买入 1卖出
        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],-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:43:55 回复(0)

Java

35岁打螺丝转Java

import java.util.*;

public class Solution {

public int maxProfit (int[] prices) {

int max = 0;

for (int i = 0; i <prices.length - 1; i++) {

for (int j = prices.length - 1 ; j > 0 & j > i; j--) {

if (prices[j] - prices[i] > max) {

max = prices[j] - prices[i];

}

return max;

}

发表于 2023-04-10 21:28:23 回复(0)

Java

Aquawer

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

发表于 2023-03-11 14:54:52 回复(0)

Java

月下拙农

public int maxProfit (int[] prices) {
    int res = 0;
    //卖出的那天收益最大，逆向思考需要卖出前某天买入时是最小的，如此一来就能保证在卖出的那天其收益最大，是非负数
    //minBuy用于记录卖出前的最小买入值
    int minBuy = prices[0];
    for (int i = 1; i < prices.length; i++) {
        res = Math.max(prices[i] - minBuy,res);
        minBuy=Math.min(prices[i],minBuy);
    }
    return res;
}

- 时间复杂度O(n)，空间复杂度O(1)

发表于 2023-02-18 13:11:49 回复(0)

Java

俺要加油

import java.util.*;


public class Solution {
    /**
     *
     * @param prices int整型一维数组
     * @return int整型
     */
    public int maxProfit (int[] prices) {
        // 创建一个数组，并计算每一天卖出时能得的最大利润，存入数组
        // 因为 今天的最大利润 = 今天的价格 - 以前的最低价格 
        // 且 昨天的最大利润 = 昨天天的价格 - 以前的最低价格 
        // 所以今天的最大利润 = 今天的价格 - 昨天的价格 + 昨天的最大利润
        int[] dp = new int[prices.length];
        int res = 0;
        dp[0] = 0;
        for (int i = 1; i < prices.length; i++) {
            dp[i] = dp[i - 1] + prices[i] - prices[i - 1] > 0 ? dp[i - 1] + prices[i] -
                    prices[i - 1] : 0;
            res = Math.max(res, dp[i]);
        }
        return res;
    }
}

发表于 2022-10-29 23:11:53 回复(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];
        int res = 0;
        dp[0] = 0;
        for(int i = 1; i < prices.length; i++){
            dp[i] = dp[i - 1] + prices[i] - prices[i - 1] > 0 ? dp[i - 1] + prices[i] - prices[i - 1] : 0;
            res = Math.max(res, dp[i]);
        }
        return res;
    }
}

发表于 2022-10-22 16:27:43 回复(0)

Java

yxjing

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][prices.length];
        for(int i=0;i<=prices.length-1;i++){
            Arrays.fill(dp[i],0);
        }
        for(int i=0;i<=prices.length-2;i++){
            for(int j=i+1;j<=prices.length-1;j++){
                if(prices[j]-prices[i]>0){
                    dp[i][j]=prices[j]-prices[i];
                }
            }
        }
        return max(dp);
    }
    public int max(int[][] arr){
        int max=arr[0][0];
        for(int i=0;i<arr.length;i++){
            for(int j=0;j<arr[0].length;j++){
                max=arr[i][j]>max?arr[i][j]:max;
            }
        }
        return max;
    }
}

发表于 2022-08-14 16:53:15 回复(0)

Java

BlueProtocol

import java.util.*;


public class Solution {
    /**
     *
     * @param prices int整型一维数组
     * @return int整型
     */
    public int maxProfit (int[] prices) {
        int len = prices.length;
        if(len < 2) {
            return 0;
        }
        int[][] maxProfit = new int[len][2];

        // 初始化
        maxProfit[0][0] = 0;
        maxProfit[0][1] = -prices[0];

        for (int i = 1; i < len; i++) {
            maxProfit[i][0] = Math.max(maxProfit[i-1][0],maxProfit[i-1][1] + prices[i]);
            maxProfit[i][1] = Math.max(maxProfit[i-1][1],-prices[i]);
        }
        return maxProfit[len-1][0];
        
    }
}

发表于 2022-07-28 13:43:57 回复(0)

Java

lizi-hust

import java.util.*;
public class Solution {
    public int maxProfit (int[] prices) {
        int n = prices.length;
        if(n==0 || n==1) return 0;
        int[] dp = new int[n];
        
        int res = 0, min = Integer.MAX_VALUE;
        for(int i=0; i<n; i++){
            min = Math.min(min, prices[i]);
            dp[i] = prices[i] - min;
            res = Math.max(res, dp[i]);
        }
        return res;
    }
}

发表于 2022-07-23 09:39:43 回复(0)

Java

艾菲尔上的铁塔梦201903182342487

动态规划算法解决：

定义dp[i]代表第i天卖出股票获得的最大利润，那么dp[i]=max{dp[i-1],prices[i]-price[j]}，也就是将前一天获得的最大利润和当天的价格减去它前面某一天的价格作比较取最大值，在实现的时候有点问题，无法取到最大值，可以用一个变量curr来记录当天的最大利润，用curr再与price[i]-price[j]进行比较，这样就能够取到最大值了。

    public static int maxProfit(int[] prices){
        int n = prices.length;
        if (n <= 1){
            return 0;
        }
        int[] dp = new int[n];
        dp[0] = 0;
        int curr = dp[0];
        for (int i = 1; i < n; i++) {
            dp[i] = dp[i-1];
            curr = dp[i];
            for (int j = 0; j < i; j++) {
                if (prices[i] > prices[j]){
                    dp[i] = Math.max(curr,prices[i]-prices[j]);
                    curr = dp[i];
                }
            }
        }
        return dp[n-1];
    }

发表于 2022-07-16 12:32:59 回复(0)

Java

小泽玛丽恩

思想便是当前环节卖出时，希望之前入手的值是最小的！

发表于 2022-05-22 00:14:56 回复(0)

Java

ljc006

// write code here
        int result=0;
        int max = 0;
        int data;
        for(int i = prices.length-1;i>=0;i--){
            max = max>prices[i]?max:prices[i];
            data = max-prices[i];
            result = result>data?result:data;
        }
            return result;

发表于 2022-05-06 11:14:37 回复(0)

Java

牛客112285422号

if(prices.length==1)
            return 0;
        //先求出来每一天之前的股票的最低价格
       int[] lowestPrice=new int[prices.length];
       lowestPrice[0]=-1;
       lowestPrice[1]= prices[0];
       for (int i=2;i< lowestPrice.length;i++){
           lowestPrice[i]=Math.min(lowestPrice[i-1],prices[i-1]);
       }
       int res=0;
        
       //遍历计算每天和该天之前股票最低价格的差，得到结果
       for (int i=1;i< prices.length;i++)
           res=Math.max(prices[i]-lowestPrice[i],res);
       return res;

发表于 2022-04-30 13:17:34 回复(0)