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).
算法思想:
既然可以買賣任意次,又要求買賣必須交替進行,這樣的話,其實也就是將所有能盈利的情況全加起來就行了,比如對於題干序列{1,2,3,1},因為2>1,盈利,所以買1錢賣2錢,因為3>2,所以買2錢賣3錢,其實這也相當於第一天買1錢,到第三天再賣3錢,一樣,因為到第四天是虧本的,所以不去花3錢買第三天的股票了。
class Solution{ public: int maxProfit(vector&prices){ int maxP=0; for(int i=1;i 0)maxP+=prices[i]-prices[i-1]; return maxP; } };