seo怎么给网站做外链,网站开发涉及技术,网站建设禁止谷歌收录的办法,自适应响应式网站源码05贪心#xff1a;买卖股票的最佳时机 II
122. 买卖股票的最佳时机 II
这道题目可能我们只会想#xff0c;选一个低的买入#xff0c;再选个高的卖#xff0c;再选一个低的买入…循环反复。
如果想到其实最终利润是可以分解的#xff0c;那么本题就很容易了#xff01…05贪心买卖股票的最佳时机 II
122. 买卖股票的最佳时机 II
这道题目可能我们只会想选一个低的买入再选个高的卖再选一个低的买入…循环反复。
如果想到其实最终利润是可以分解的那么本题就很容易了
如何分解呢
假如第 0 天买入第 3 天卖出那么利润为prices[3] - prices[0]。
相当于(prices[3] - prices[2]) (prices[2] - prices[1]) (prices[1] - prices[0])。
此时就是把利润分解为每天为单位的维度而不是从 0 天到第 3 天整体去考虑
那么根据 prices 可以得到每天的利润序列(prices[i] - prices[i - 1])…(prices[1] - prices[0])。
局部最优收集每天的正利润全局最优求得最大利润。
class Solution {public int maxProfit(int[] prices) {//除了第一天每天都有利润int profit 0;int sumProfit 0;int pre prices[0];//记录上一次的价格for(int i 1; i prices.length; i) {profit prices[i] - pre;if(profit 0) {sumProfit profit;}pre prices[i];//更新前面的价格我需要的是每天的利润抛弃负利润,那7 1 5距离pre7now1为-6抛弃的所以更新pre不加利润就是不要7买1卖接着就是看1,5正利润所以要加上要1买5卖}return sumProfit;}
}
