Say you have an array for which the ith element is the PRice of a given stock on day i.
Design an algorithm to find the maximum profit. You may complete as many transactions as you like (ie, buy one and sell one share of the stock multiple times). However, you may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).
s思路： 1. 和 Leetcode 121. Best Time to Buy and Sell Stock不一樣，前一道題要求只能最多買賣一次找最大profit;這道題要求可以多次交易。 2. 初看道題，有點覺得下不了手，想到在121題一次交易時需要兩個變量lowprice和profit，那么多次交易不得需要多個變量啊？？其實，多次反而不用這些求最小值的過程，遍歷一遍，遇到比lowprice大的就直接把差值加在profit上，然后把lowprice更新成這個值，繼續找，再次遇到比現在lowprice大的，繼續把差值加在profit上，然后把這個值賦給lowprice。可以看出，只要有利可圖(后面值比前面大)，就reap it。然后更新lowprice。 3. 這種有很強方向性的題目，即：后面的數大于前面的數，而遍歷又是從左往右。一般有o(n) 4. 方法2參考了之前做的，就是遍歷一遍，比較前后兩個數的大小，如果當前數比前一個數大，則把差值加在profit。不用計算lowprice.這才是終極的解法！因為要求不是一次、也不是兩次交易，要求無限次交易，所以就沒有必要找最小值了，反而簡單！
//方法1：和方法2比，有些復雜，但物理意義清楚class Solution {public: int maxProfit(vector<int>& prices) { // int lowprice=INT_MAX; int profit=0; for(int i=0;i<prices.size();i++){ lowprice=min(lowprice,prices[i]); if(prices[i]>lowprice){ profit+=prices[i]-lowprice; lowprice=prices[i]; } } return profit; }};//方法2：簡潔class Solution {public: int maxProfit(vector<int>& prices) { // int profit=0; for(int i=1;i<prices.size();i++){ if(prices[i]>prices[i-1]) prifit+=prices[i]-prices[i-1]; } return profit; }};新聞熱點
疑難解答
