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

晓宇普通 2024年12月29日下午3:23

class Solution {
public:
// 思路：出售时刻在购得时刻之后，对于当前时刻，最大收益是在未来最大售价时抛售。从末尾时刻向起始时刻求解，避免在重复序列求最大售价。
    int bestTiming(vector& prices) {
        if(prices.empty()) return 0;
        int n = prices.size();
 
        int res = 0;
        int max_price = prices[n - 1];  // 最大出售价格
        for(int i = n - 2; i >= 0; i--){
            if(prices[i] > max_price) max_price = prices[i];
            res = max(max_price - prices[i], res);
        }
        return res;
    }
    // o(n) o(1)
};

0 赞同 0 条回复

陆狗陆狗普通 2024年12月26日上午9:32

解题思路
– 定义dp[i]，表示以(0,i)这个区间内的最大利润，还需要额外定义一个变量min表示最低价格
– dp[i]=Max(dp[i-1],prices[i]-min),并且更新min
– dp[0]=0,min=prices[0]
【题解1】自己的解法，能通过“连续和最大值”悟出可以dp定义的灵活性，已经创造性得把临时变量minValue引入，其实已经很不错了

class Solution {
    public int bestTiming(int[] prices) {
        // 1.定义dp[i]，表示以(0,i)这个区间内的最大利润，还需要额外定义一个变量min表示最低价格
        // 2.dp[i]=Max(dp[i-1],prices[i]-min),并且更新min
        // 3.dp[0]=0,min=prices[0]

        // 【错误点】边界值，否则dp[0]要报错
        if (prices.length == 0) {
            return 0;
        }

        int[] dp = new int[prices.length];
        dp[0] = 0;
        int minValue = prices[0];
        for (int i = 1; i < prices.length; i++) {
            dp[i] = Math.max(dp[i - 1], prices[i] - minValue);
            minValue = Math.min(minValue, prices[i]);
        }
        return dp[prices.length - 1];

    }
}

错误点1：边界值，要考虑prices=[]的情况，否则dp[0]要报错
【题解2】 dp[]优化成1个变量

class Solution {
    public int bestTiming(int[] prices) {
         // 【优化】从int[]优化成1个变量，因为dp[i]只和上一个dp[i-1]有关，所以可以进行简化
        int target = 0;
        // 【优化】给一个默认值Integer.MAX_VALUE，并且循环从0开始，就可以兼容prices=[]的这种情况了
        int minValue = Integer.MAX_VALUE;
        for (int i = 0; i < prices.length; i++) {
            target = Math.max(target, prices[i] - minValue);
            minValue = Math.min(minValue, prices[i]);
        }
        return target;
    }
}

0 赞同 0 条回复

Aatorx 永久会员 2024年12月23日上午10:53

class Solution {
public:
    int bestTiming(vector<int>& prices) {
        if(prices.empty()) {
            return 0;
        }
        int low = prices[0];
        int dp = 0;
        for(int i = 1; i < prices.size(); i++) {
            low = min(low, prices[i]);
            dp = max(dp, prices[i] - low);
        }
        return dp;
    }
};

时间复杂度O(N)，空间复杂度O(1)。

0 赞同 0 条回复

Pendulumpal 普通 2024年12月22日下午5:49

一次遍历，O(n)

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

0 赞同 0 条回复

秋山丽奈普通 2024年12月22日下午4:56

思路：本题目只能买卖一次，若可买卖多次使用状态机

class Solution {

    int[][] memo ;

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

    public int bestTiming_muiltDay(int[] prices) {
        int day = prices.length;
        this.memo = new int[day][2];

        return dfs(prices, day-1, 0);
    }

    public int dfs(int[] prices, int day, int buyFlag){
        if(day < 0){
            return buyFlag == 0? 0: Integer.MIN_VALUE;
        }

        if(this.memo[day][buyFlag] != 0){
            return this.memo[day][buyFlag];
        }

        if(buyFlag == 1){
            // 今天持有 -> 昨天已持有/昨天未持有今天买入 
            this.memo[day][buyFlag] = Math.max(dfs(prices, day-1, buyFlag), dfs(prices, day-1, 1-buyFlag) - prices[day]);

            return this.memo[day][buyFlag];
        }else{
            // 今天未持有 -> 昨天未持有/昨天持有今天卖出 
            this.memo[day][buyFlag] = Math.max(dfs(prices, day-1, buyFlag), dfs(prices, day-1, 1-buyFlag) + prices[day]);

            return this.memo[day][buyFlag];
        }
    }
}

0 赞同 0 条回复

苯庸普通 2024年12月21日下午9:01

class Solution {
public int bestTiming(int[] prices) {
if(prices.length 0) return 0;
int[][] dp = new int[prices.length][2];
dp[0][1] = -prices[0];
for(int i = 1; i < prices.length; 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], – prices[i]);
}
return dp[prices.length-1][0];
}
}
思路：只能买卖一次，所以买入是dp[i][1] = Math.max(dp[i-1][1], – prices[i]);
时间：O（n）
空间：O（n）

0 赞同 0 条回复

Kisara 普通 2024年12月21日下午8:02

动态规划

class Solution {
    public int bestTiming(int[] prices) {
        if(prices==null||prices.length<=0) return 0; 
        int piovit = 0;
        int cost = prices[0];
        for (int i = 1; i < prices.length; i++) {
            cost = Math.min(cost, prices[i]);
            piovit = Math.max(piovit, prices[i] - cost);
        }
       return piovit<=0?0:piovit;
    }
}

0 赞同 0 条回复

月下足迹普通 2024年12月21日上午11:31

public int bestTiming(int[] prices) {
if(prices.length 0) return 0;
int min = prices[0];
int n = prices.length;
int profit = Integer.MIN_VALUE;
int [] dp = new int [n];
dp[0] = 0;
for (int i = 1; i < n; i++) {
min = Math.min(min, prices[i]);//找最低价格
dp[i] = Math.max(dp[i – 1], prices[i] – min);
}
for (int i = 0; i < n; i++) {
profit = Math.max(profit, dp[i]);
}
return profit;
}

0 赞同 0 条回复

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

共以下 8 个回答

# 回答此问题取消回复

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

共以下 8 个回答

# 回答此问题 取消回复

# 回答此问题取消回复