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; }};新闻热点
疑难解答
