剑指 Offer 63. 股票的最大利润

剑指 Offer 63. 股票的最大利润

• 解题思路
• 代码

解题思路

直接动态规划。

• dp数组含义：dp[i]代表 前 i 日的最大利润
• 状态转移方程：前i日最大利润=max(前(i−1)日最大利润,第i日价格−前i日最低价格)

代码

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

        int[] dp=new int[prices.length+1];
        int min=prices[0];
        //dp[i] 代表 前 i 日的最大利润
        dp[0]=0;//第0天的利润为0

        for(int i=1;i<=prices.length;i++){
            min=Math.min(min,prices[i-1]);
            //注意这里：prices[i-1],就是第一天的价格，假如i=1,i-1=0;prices数组下标为0，就是第一个元素，也即第一天
            dp[i]=Math.max(dp[i-1],prices[i-1]-min);
        }

        return dp[prices.length];
    }
}