【动态规划专题】剑指 Offer 63. 股票的最大利润-跟着帅地玩副业，开拓第二曲线PlayOffer

hi 普通 2023年11月20日下午11:34

动态规划股票买卖问题通用做法

class Solution {
public:
    int bestTiming(vector<int>& prices) {
        int n = prices.size();
        if(n == 0) return 0;

        int dp[100010][2];

      //第0天不持有芯片能获得的最大价值
        dp[0][0] = 0;
      //第0天持有芯片能获得的最大价值
        dp[0][1] = -prices[0];

        for(int i = 1; i <= n - 1; 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];
    }
};

循环数组，依据变化着的（可能不变）最小值和最大值求出当前最大利润

class Solution {
public:
    int bestTiming(vector<int>& prices) {
        if(prices.size() == 0) return 0;
        int minp = prices[0];
        int maxprof = 0;

        for(int i = 1; i <= prices.size() - 1; i++){
            minp = min(minp, prices[i]);
            maxprof = max(maxprof, prices[i] - minp);
        }

        return maxprof;
    }
};

0 赞同 0 条回复

June 普通 2023年10月9日下午9:10

class Solution {
    public int bestTiming(int[] prices) {
        if ( prices.length == 0 )
            return 0;
        int minn = prices[0]; // 记录到目前为止最低的买入价
        int earn = 0;
        for(int i=1;i<prices.length;i++) {
            earn = Math.max(earn, prices[i] - minn);
            minn = Math.min(minn,prices[i]);
        }
        return earn;
    }
}

0 赞同 0 条回复

Marshan 普通 2023年8月29日下午4:25

时间O(n),空间O(1)

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        if(n == 0 || n == 1){
            return 0;
        }
        // dp[i]表示在第i+1天能获得的最大利润
        // vector<int> dp(n,0);
        int res = 0;
        int minValue = prices[0];
        for(int i = 1;i < n;++i){
            res = max(res,prices[i] - minValue);
            minValue = min(minValue,prices[i]);
        }

        // for(int item:dp){
        //     res = max(res,item);
        // }
        return res;
    }
};

0 赞同 0 条回复

mpweixin用户普通 2023年8月21日下午12:40

class Solution {
    public int maxProfit(int[] prices) {
        if (prices.length==0) return 0;
        // 输入: [7,1,5,3,6,4]
        //输出: 5
        //解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
        //     注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格。
        int[] dp = new int[prices.length];
        dp[0] = 0;
        int min = prices[0];
        for (int i = 1; i < prices.length; i++) {
            if (prices[i] < min) min = prices[i];
            dp[i] = Math.max(dp[i-1], prices[i]-min);
        }
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < dp.length; i++) {
            if (dp[i] > max) {
                max = dp[i];
            }
        }
        return max;
    }
}

0 赞同 0 条回复

人生何处不青山普通 2023年8月20日下午9:49

基础中的基础题

function maxProfit(prices: number[]): number {
    let res = 0, prev = Infinity;
    for (let i = 0; i < prices.length; i++) {
        res = Math.max(res,prices[i] - prev);
        prev = Math.min(prev,prices[i]);
    }
    return res;
};

0 赞同 0 条回复

北辰普通 2023年8月15日下午9:48

class Solution {
    public int maxProfit(int[] prices) {
        if(prices.length<2) return 0;
        int n = prices.length;
        int[] dp = new int[n];
        dp[0]=0;
        int cost = prices[0];
        for(int i=1;i<n;i++) {
            dp[i] = Math.max(dp[i-1], prices[i]-cost);
            cost = Math.min(cost, prices[i]);
        }
        return dp[n-1];
    }
}

时间复杂度：O（n）
空间复杂度：O（n）

0 赞同 0 条回复

Mby 普通 2023年8月14日下午7:29

class Solution {
    public int maxProfit(int[] prices) {
        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;
        //时间复杂度：O(n)
        //空间复杂度：O(1)
    }
}

0 赞同 0 条回复

NullPointerException 普通 2023年8月8日下午3:51

class Solution {
public int maxProfit(int[] prices) {
//记录上一个最大利润值要么取上一个，要么自己-min
int dp[]=new int[prices.length+1];
if(prices.length0||prices
null)
{
return 0;
}
int min = prices[0];
dp[0]=0;
for(int i=1;i<dp.length;i++)
{
dp[i]=Math.max(dp[i-1],prices[i-1]-min);
min=Math.min(min,prices[i-1]);
}
return dp[dp.length-1];
}
}

0 赞同 0 条回复

阿尚普通 2023年8月7日下午4:35

class Solution {
    public int maxProfit(int[] prices) {
        if(prices == null || prices.length == 0) return 0;
        //dp[i][0]:第i天持有股票的最大利润    dp[i][1]:第i天不持有股票的最大利润
        int[][] dp = new int[prices.length][2];
        dp[0][0] = -prices[0];//初始化第0天持有股票最大利润
        dp[0][1] = 0;//初始化第0天不持有股票最大利润
        for(int i = 1; i < prices.length; i++){
            dp[i][0] = Math.max(dp[i - 1][0], 0 - prices[i]);
            dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] + prices[i]);
        }

        return dp[prices.length - 1][1];
    }
}

0 赞同 0 条回复

长河呼叫黄江普通 2023年8月6日下午11:15

8.6
Day27：下面是代码

class Solution {
    public int maxProfit(int[] prices) {
        int minprice = Integer.MAX_VALUE;
        int maxprofit = 0;
        for(int i = 0; i < prices.length; i++){
            if(prices[i] < minprice){
                minprice = prices[i];
            }else if(prices[i] - minprice >= maxprofit){
                maxprofit = prices[i] - minprice;
            }
        }
        return maxprofit;
    }
}

0 赞同 0 条回复

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

共以下 10 个回答

# 回答此问题取消回复

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

共以下 10 个回答

# 回答此问题 取消回复

# 回答此问题取消回复