[Leetcode LCR188.][Medium]-买卖芯片的最佳时机-dp/状态压缩

目录

一、题目描述

二、整体思路

三、代码

---

一、题目描述

原题地址

二、整体思路

1. 可以设一个长度为price.length的dp数组,dp[i]表示到第i天时的最大利润。因为买入操作只能在卖出操作之前完成,因此需要记录下遍历prices数组到第i天时历史最低价格minp,每次遍历都要更新历史最低价格,状态转移方程为dp[i]=Math.max(dp[i-1],prices[i]-minp)
2. 对于每个dp[i],只会用到前一天的最大利润即dp[i-1],那么可以进行状态压缩,将dp一维数组压缩成一个int。

三、代码

class Solution {//一维dp数组
    public int bestTiming(int[] prices) {
        if(prices.length==0){
            return 0;
        }
        int minp=prices[0];
        int dp[]=new int[prices.length];
        dp[0]=0;
        for(int i=1;i<prices.length;i++){
            if(prices[i]<minp){
                minp=prices[i];
            }
            dp[i]=Math.max(prices[i]-minp,dp[i-1]);
        }
        return dp[prices.length-1];
    }
}

class Solution {
    public int bestTiming(int[] prices) {
        int res=0;//状态压缩后
        if(prices.length==0){
            return res;
        }
        int minp=prices[0];
        for(int i=0;i<prices.length;i++){
            if(prices[i]<minp){
                minp=prices[i];
            }
            res=Math.max(prices[i]-minp,res);
        }
        return res;
    }
}

原文地址：https://blog.csdn.net/2201_75413354/article/details/142692912

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！