Leetcode 122 买卖股票的最佳时机 II

题意理解：

? ? ? ? 已知：一个整数数组?prices?，其中?prices[i]?表示某支股票第?i?天的价格

? ? ? ? 如何哪个时间点买入，哪个时间点卖出，多次交易，能够收益最大化

? ? ? ? 目的：收益最大化

解题思路：

? ? ? ? 使用贪心思路来解题，需要明确什么时局部最优解，如何由局部最优解推导全局最优解。

? ? ? ? 首先我们要尽可能的利益最大化，就要尽可能的保证利益为正。

? ? ? ? 这里引入利益区间的概念及：[买入，卖出]? 利益=卖出-买入

? ? ? ? 例如： [7,1,5,3,6,4]

? ? ? ? eg:利益区间[0,3]? ?

?????????????利益=p[3]-p[0]

? ? ? ? ? ? ? ? ? ? =p[3]-p[2]+p[2]-p[1]+p[1]-p[0]

? ? ? ? ? ? ? 实际是每天利益的和，由此可知，我们要保证利益尽可能的大

? ? ? ? ? ? ? 即收集所有正的天利益即可得到，这个规定时间内的最大获益。

1.贪心解题

? ? ? ? 我们使用result来记录最大利益，同时我们需要两个指针一个指向买入天，一个指向卖出天，来计算当前交易利益

? ? ? ? 注意：若交易会损失钱则可选择不交易，所以result的初始化为0。

public int maxProfit(int[] prices) {
        int result=0;
        //第一天不卖出，最后一天不买入
        for(int i=1;i<prices.length;i++){
            result+=Math.max(prices[i]-prices[i-1],0);//总是叠加正的利益
        }
        return result;
    }

2.分析

时间复杂度：O(n)

空间复杂度：O(n)

n是prices数组的长度。