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

Gg 普通 2023年8月6日下午10:56

class Solution {
    // 1、定义dp数组为 截止到i天的最大利润
    // 2、递推公式 。dp[i] = max(dp[i-1],prices[i] - min(prices[0:i]))
    // 3、初始化
    // 4、遍历方向
    // 5、举例
    public int maxProfit(int[] prices) {
        if(prices.length == 0){
            return 0;
        }
        int[] dp = new int[prices.length];
        int min = prices[0];
        dp[0] = 0;
        for(int i = 1; i < prices.length; i ++){
            // 计算
            dp[i] = Math.max(dp[i-1],prices[i] - min);
            min = Math.min(min,prices[i]);
        }
        return dp[prices.length-1];

    }
}

0 赞同 0 条回复

宁永久会员 2023年3月14日下午2:53

计算过程中直接记录当前出现过的最大最小值也可以，这时对于数组的遍历需要从0开始

class Solution {
    public int maxProfit(int[] prices) {
        if(prices == null || prices.length == 0){
            return 0;
        }
        //不只是找到最小值和最大值
        //要么是0 要么是今天减去昨天再加上昨天的最大收益
        int dp = 0;
        int max = 0;
        for(int i = 1; i < prices.length; i ++){
            dp = Math.max(0, dp + prices[i] - prices[i - 1]);
            max = Math.max(dp, max);
        }
        return max;
    }
}
class Solution {
    public int maxProfit(int[] prices) {
        if(prices == null || prices.length == 0){
            return 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 条回复

PatNick 普通 2023年1月18日下午5:57

def maxProfit(prices: list[int]) -> int:
    min = prices[0]
    max_ = 0

<pre><code>for _ in range(1,len(prices)):
    if min > prices[_]:
        min = prices[_]
    else:
        # 更新最大利润
        max_ = max(prices[_] - min,max_)

return max_
</code></pre>

0 赞同 0 条回复

lucca 普通 2023年1月18日下午1:35

迭代

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

// 寻找 max(prices[j] -  prices[i]) [j > i]
class Solution {
    public int maxProfit(int[] prices) {
        if (prices.length == 0) return 0;
        int min = prices[0];
        int ans = 0;
        for (int num : prices) {
            ans = Math.max(ans, num - min);
            min = Math.min(min, num);
        }
        return ans;
    }
}

0 赞同 0 条回复

@ 普通 2022年12月19日上午10:30

时间复杂度：O(N)

空间复杂度：O(1)

class Solution {
    public int maxProfit(int[] prices) {
        if(prices.length == 0)
            return 0;

        int p = 0;
        int m = prices[0];

        for (int i = 1; i < prices.length; i++) {
            if (prices[i] < prices[i - 1])
                m = prices[i];
            else {
                if (prices[i] - m > p)
                    p = prices[i] - m;

                prices[i] = m;
            }


        }

        return p;

    }

    //优化
    public int maxProfit2(int[] prices) {
        int min = Integer.MAX_VALUE;
        int p = 0;

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

0 赞同 0 条回复

派大星普通 2022年12月2日下午11:12

class Solution {
//时间复杂度O(n)
//空间复杂度O(1)
    public int maxProfit(int[] prices) {
         if(prices.length==0)
             return 0;
         int min=prices[0];
         int max=0;
         for(int i=0;i<prices.length;i++){
             min=Math.min(min,prices[i]);
             max=Math.max(max,prices[i]-min);
         }
        return max;
    }
}

0 赞同 0 条回复

你有点可爱喔普通 2022年12月1日下午10:04

class Solution {
    public int maxProfit(int[] prices) {
            //dp动态规划
            //1、5步走; 
            //1. 确定dp数组以及下标的含义;2、递推公式  3、初始化、4、遍历顺序
            if (prices.length == 0){
                return 0;
            }
            int [] dp = new int[prices.length];
            dp[0] = 0;
            int min = prices[0];
            for (int i = 1;i<prices.length;i++){
                min = Math.min(prices[i],min);
                dp[i]  = Math.max(dp[i-1],prices[i]-min);
            }
            return dp[prices.length-1];
    }
}

0 赞同 0 条回复

T 普通 2022年11月30日下午9:28

class Solution {
    public int maxProfit(int[] prices) {
        if(prices.length == 0) return 0;
        int n = prices.length;
        //dp[i]用来记录i天中最大利润
        int[] dp = new int[n];
        dp[0] = 0;
        int cost = prices[0];
        for(int i = 1; i < prices.length; i++) {
            //更新最小买入价
            cost = Math.min(cost, prices[i]);
            //当前价-买入价 跟 前一日最大利润进行比较
            dp[i] = Math.max(dp[i - 1], prices[i] - cost);

        }
        return dp[n - 1]; 
    }
}

0 赞同 0 条回复

y 普通 2022年11月27日下午3:32

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

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

0 赞同 0 条回复

mpweixin用户普通 2022年11月26日下午8:33

C++

很简单的一道dp
class Solution {
public:
int maxProfit(vector& prices) {
int len = prices.size();
vector dp(len+1);
dp[0] = 0;
if(len <= 1) return 0;
int minn = prices[0];
for(int i = 1; i < prices.size(); ++i) {
dp[i] = max(prices[i] – minn, dp[i-1]);
if(minn > prices[i]) minn = prices[i];
}
return dp[len-1];
}
};

0 赞同 0 条回复

西西弗斯的石头永久会员 2022年11月25日下午10:03

时间复杂度O（n），空间复杂度为O（1）

class Solution {
    public int maxProfit(int[] prices) {
        int m = prices.length;
        int x = Integer.MAX_VALUE;
        int dp = 0;
        for(int i = 0;i < m;i++){
            x = Math.min(x,prices[i]);
            if(prices[i] - x > 0){
                dp = Math.max(prices[i] - x,dp);
            }

        }
        return dp;
    }
}

0 赞同 0 条回复

青木普通 2022年11月24日下午9:17

/**
    直接维护一个dp，dp表示遍历过的股票价格中最低的价格
    有个坑是这里数组长度可能为0，所以dp的初始值得自己设置，我就设置成最大的int了

    时间O(n)
    空间O(1)
 */

class Solution {
    public int maxProfit(int[] prices) {
        int ans = 0;
        int dp = 0x7fffffff;
        for(int price : prices){
            dp = Math.min(price, dp);
            ans = Math.max(ans, price - dp);
        }
        return ans;
    }
}

0 赞同 0 条回复

So 普通 2022年11月24日上午10:22

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 条回复

訁訁訁訁訁普通 2022年11月24日上午12:27

均是O(N)

//dp[i][0] 是第i天持有股票的收益 dp[i][1]是第i天不持有股票的收益
class Solution {
    public int maxProfit(int[] prices) {
        if(prices.length == 0 )return 0;
        int len = prices.length;
        int[][] dp = new int[len][2];
        dp[0][0] = -prices[0];
        for(int i = 1;i < len;i++){
            dp[i][0] = Math.max(dp[i - 1][0],-prices[i]);
            dp[i][1] = Math.max(dp[i - 1][1],dp[i - 1][0] + prices[i]);
        }
        return dp[len - 1][1];
    }
}

0 赞同 0 条回复

Tolkien 永久会员 2022年11月23日下午10:41

/**
     * 动态规划
     * 时间复杂度：O(n)
     * 空间复杂度：O(n)
     * 1. dp数组的定义：前i天的股票中买卖一次能获得的最大利率
     * 2. 关系式：若第i天没卖，则dp[i] = dp[i-1];
     * 若第i天卖出，则dp[i] = prices[i]-min(prices[0:i-1])
     * 3. 初始化：dp[0] = 0
     */
    public static int maxProfit(int[] prices) {
        int length = prices.length;
        if (length == 0) {
            return 0;
        }

        int[] dp = new int[length];
        dp[0] = 0;
        int min = prices[0];

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

        return dp[length-1];
    }

    /**
     * 动态规划
     * 时间复杂度：O(n)
     * 空间复杂度：O(1)
     */
    public static int maxProfitOptimized (int[] prices) {
        int length = prices.length;
        if (length == 0) {
            return 0;
        }

        int dp = 0;
        int min = prices[0];

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

        return dp;
    }

0 赞同 0 条回复

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

共以下 15 个回答

迭代

# 回答此问题取消回复

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

共以下 15 个回答

迭代

# 回答此问题 取消回复

# 回答此问题取消回复