【动态规划专题】剑指 Offer 63. 股票的最大利润

本问题对应课程链接：剑指offer刷题第六期

要求：

1、请打卡你的解题代码，如果能简单说一下思路则简单说一下思路。
2、给出你代码所用的时间复杂度和空间复杂度

shuaidi

更新于 3 年前 175 14

共以下 14 个回答

kfaebot 普通 2024年5月11日上午9:54

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        vector<vector<int>> dp(prices.size(),vector<int>(2));

        if(prices.size()==1){
            return 0;
        }

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

        //状态转移方程
        for(int i=1;i<prices.size();i++){
            dp[i][0]=max(dp[i-1][0],dp[i-1][1]+prices[i]);
            dp[i][1]=max(dp[i-1][1],-prices[i]);
        }
        return dp[prices.size()-1][0];
    }
};

0 赞同 0 条回复

Thaddeus 永久会员 2024年5月6日上午9:09

打卡

class Solution {
    public int bestTiming(int[] prices) {
        int res = 0, minPrice = Integer.MAX_VALUE;
        for(int i = 0; i < prices.length; i++) {
            minPrice = Math.min(minPrice, prices[i]);
            res = Math.max(res, prices[i] - minPrice);
        }
        return res;
    }
}

0 赞同 0 条回复

=.= 普通 2024年4月15日下午2:28
class Solution {
public int bestTiming(int[] prices) {
int n = prices.length;
if(n <= 1) return 0;
```
    int min = prices[0];
    int ans = 0;

    for(int i=1; i<n; i++){
        ans = Math.max(ans, prices[i] - min);
        min = Math.min(min, prices[i]);
    }

    return ans;
}
```
}

时间：O(n)
空间：O(1)
0 赞同 0 条回复

登录以回复
神经蛙普通 2024年4月2日下午11:32

class Solution {
public:
int bestTiming(vector& prices) {
int minPrice = INT_MAX;
int maxProfit = 0;
for (int price : prices) {
if (price < minPrice) {
minPrice = price;
} else {
maxProfit = max(maxProfit, price – minPrice);
}
}
return maxProfit;
}
};
打卡

0 赞同 0 条回复

登录以回复

白雪公主倒拔垂杨柳永久会员 2024年4月2日下午8:56

class Solution {
    public int bestTiming(int[] prices) {
        //错误！本题只能买卖一次芯片
        // if(prices==null || prices.length==0) return 0;
        // int len = prices.length;
        // int[][] dp = new int[len][2]; // dp[i][j]:第i天买入 第j天卖掉
        // dp[0][0]=0;//第一天不操作
        // dp[0][1]=-prices[0]; //第一天买入

        // for(int i=1;i<len;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[len-1][0];

        int min = Integer.MAX_VALUE;
        int max = 0;

        for(int i = 0; i < prices.length; i++){
            if(prices[i] < min){
                min = prices[i];
            }else{
                max = Math.max(max, prices[i] - min);
            }
        }
        return max;

    }
}

0 赞同 0 条回复

方铎码农普通 2024年4月1日下午11:24

class Solution {
    public int bestTiming(int[] prices) {
        int cost = Integer.MAX_VALUE, profit = 0;
        for(int price : prices) {
            cost = Math.min(cost,price);
            profit = Math.max(profit, price - cost);
        }
        return profit;
    }
}

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

0 赞同 0 条回复

heathhou 普通 2024年4月1日下午10:46

class Solution {
public:
    int bestTiming(vector<int>& prices) {
        if(prices.size() <= 1){
            return 0;
        }
        int minPrice = INT_MAX;
        int maxPrice = 0;

        for(int price : prices){
            if(price < minPrice){
                minPrice = price;
            }else{
                maxPrice = max(maxPrice, price-minPrice);
            }
        }

        return maxPrice;
    }
};

时间复杂度：O(n)
空间复杂度：O(1)

0 赞同 0 条回复

Jimmy 普通 2024年4月1日下午10:04

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

class Solution {
public:
    int bestTiming(vector<int>& prices) {
        int cost = INT_MAX,profit = 0;
        for(int price : prices)
        {
            cost = min(cost,price);
            profit = max(profit,price-cost);
        }
        return profit;
    }
};

0 赞同 0 条回复

云无深雁影普通 2024年4月1日下午3:57
class Solution {
public int bestTiming(int[] prices) {
int cost = Integer.MAX_VALUE;
int profit = 0;
for(int price: prices){
cost = Math.min(price,cost);
profit = Math.max(price – cost, profit);
}
return profit;
```
}
```
}
//时间复杂度On
//空间复杂度O1
0 赞同 0 条回复

登录以回复
一个达不刘普通 2024年4月1日上午11:25
class Solution {
public:
int bestTiming(vector& prices) {
//dp[i][0]_第i天没有股票的最大利润
int n = prices.size();
if(n0) return 0;
int dp[n][2];
dp[0][0] = 0;
dp[0][1] = -prices[0];
```
    for(int i =1;i<n;i++){
        dp[i][0] = max(dp[i-1][0], dp[i-1][1]+prices[i]);
        dp[i][1] = max(dp[i-1][1], -prices[i]);
    }

    return dp[n-1][0];

}
```
};
0 赞同 0 条回复

登录以回复

紫芝普通 2024年4月1日上午8:05

时间复杂度：O(n)
空间复杂度：O(1)

func bestTiming(prices []int) int {
    if len(prices) <= 0 { return 0 }
    minprice := prices[0]
    maxprofit := 0
    for i:=1; i<len(prices); i++ {
        if prices[i] < minprice {
            minprice = prices[i]
        } 
        maxprofit = max(maxprofit, prices[i]-minprice)
    }
    return maxprofit
}

0 赞同 0 条回复

机电皮怪永久会员 2024年3月31日下午11:06
时间复杂度O(N),空间复杂度O(1)

“`C++
class Solution {
public:
int bestTiming(vector& prices) {
if(prices.size() <= 1) { return 0; } int min = 99999; int profit = 0; for(int money : prices) { if(min > money)
{
min = money;
}
else
{
profit = max(money – min, profit);
}
}
```
    return profit;
}
```
};

“`
0 赞同 0 条回复

登录以回复
Raphtalia. 普通 2024年3月31日下午10:56

class Solution {
public:
int bestTiming(vector& prices) {
int profit = 0;
int cost = INT_MAX;
for(auto c : prices) {
cost = min(cost, c);
profit = max(profit, c – cost);
}
return profit;
}
};
//时间复杂度O(N)
//空间复杂度O(1)

0 赞同 0 条回复

登录以回复

王位詮釋普通 2024年3月31日下午8:11

class Solution {
    public int bestTiming(int[] prices) {
        if(prices.length<=0){
            return 0;
        }
        int max = 0;//股票最大收益
        int min = prices[0];
        for(int i=1;i<prices.length;i++){
            min = min>prices[i]?prices[i]:min;
            max = max<(prices[i]-min)?prices[i]-min:max;
        }
        return max;
    }
}
时间复杂度：O(n)
空间复杂度：O(1)
这个题最开始的时候是想要通过暴力法求解的，但是可能会有超时的问题，所以我们可以通过一次遍历，遍历的时候记录到目前为止最便宜的股票价格，如果后续遍历过程中某一天股票价格比min大，则可以计算max，max代表当前为止可以获得的最大的收益。

0 赞同 0 条回复

# 回答此问题取消回复

后才能回答

【动态规划专题】剑指 Offer 63. 股票的最大利润

共以下 14 个回答

# 回答此问题 取消回复

# 回答此问题取消回复