网站文章怎么做标签百度一下首页百度一下

题意理解：

        已知：一个整数数组 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数组的长度。