方法一  贪心算法

思路：

1、局部最优：截止到当天能赚到的最大利润

2、全局最优：截止到最后一天能赚到的最大利润就是全局最大利润

例子：上升就是赚钱机会，贪心地将每个赚钱机会把握住，获取赚到的钱的总和即可

class Solution {
    public int maxProfit(int[] prices) {
        int res = 0;
        for (int i = 0; i < prices.length - 1; i++){
            int delta = prices[i + 1] - prices[i];
            if (delta > 0) res += delta; // 贪心算法，不放过截止到现在的所有赚钱机会
        }
        return res;
    }
}

• 时间复杂度: O(n)，for循环遍历一次数组
• 空间复杂度: O(1)，没有额外的空间开销

方法二  动态规划

思路：

1、确定dp[i]的含义：截止到第i天赚到的最多的钱

2、确定递推关系：dp[i] = dp[i-1] + today

3、确定初始值：第一天赚到的最多的钱肯定是0，即dp[0] = 0

class Solution {
    public int maxProfit(int[] prices) {
        int dp = 0;
        for (int i = 1; i < prices.length; i++){
            // 今天之前赚到的最多的钱 + 今天当天赚到最多的钱 = 包括今天在内已经赚到的最多的钱
            int today = prices[i] - prices[i-1] > 0 ? prices[i] - prices[i-1] : 0;
            dp += today;
        }
        return dp;
    }
}

• 时间复杂度: O(n)，for循环遍历一次数组
• 空间复杂度: O(1)，dp[i]只与dp[i-1]有关，只用一个变量记录值即可

---