[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;
    }
}