LeetCode 122.Best Time to Buy and Sell Stock II(株を売買する最適なタイミングII)

タイトルの説明:
配列が与えられ、そのi番目の要素は、与えられた株のi日目の価格です.
あなたが得られる最大利益を計算するアルゴリズムを設計します.できるだけ多くの取引(株を複数回売買する)を完了することができます.
注意:複数の取引に同時に参加することはできません(再購入前に前の株を売却しなければなりません).
例1:

  : [7,1,5,3,6,4]
  : 7
  :    2  （     = 1）     ，   3  （     = 5）     ,            = 5-1 = 4 。
       ，   4  （     = 3）     ，   5  （     = 6）     ,            = 6-3 = 3 。

例2:

  : [1,2,3,4,5]
  : 4
  :    1  （     = 1）     ，   5   （     = 5）     ,            = 5-1 = 4 。
             1     2        ，        。
                    ，                 。

例3:

  : [7,6,4,3,1]
  : 0
  :       ,       ,         0。

 
 
AC C++ Solution:
問題解決の考え方:
1つのシーケンスが「a<=b<=c<=d」であると仮定すると、利益は「d−a=(b−a)+(c−b)+(d−c)」であることは間違いない.もう1つが「a<=b>=b'<=c<=d」であると仮定し,利益は「(b−a)+(d−b')」と計算するのは難しくない.したがって、増分シーケンスの差だけを計算すると最大利益になります.
 

class Solution {
public:
    int maxProfit(vector &prices) {
        int ret = 0;
        for (size_t p = 1; p < prices.size(); ++p) 
            ret += max(prices[p] - prices[p - 1], 0);    
        return ret;
    }
};