# Best Time to Buy and Sell Stock II ### Source - leetcode: [Best Time to Buy and Sell Stock II | LeetCode OJ](https://leetcode.com/problems/best-time-to-buy-and-sell-stock-ii/) - lintcode: [(150) Best Time to Buy and Sell Stock II](http://www.lintcode.com/en/problem/best-time-to-buy-and-sell-stock-ii/) ~~~ 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). Example Given an example [2,1,2,0,1], return 2 ~~~ ### 題解 賣股票系列之二，允許進行多次交易，但是不允許同時進行多筆交易。直覺上我們可以找到連續的多對波谷波峰，在波谷買入，波峰賣出，穩賺不賠~ 那么這樣是否比只在一個差值最大的波谷波峰處交易賺的多呢？即比上題的方案賺的多。簡單的證明可先假設存在一單調上升區間，若人為改變單調區間使得區間內存在不少于一對波谷波峰，那么可以得到進行兩次交易的差值之和比單次交易大，證畢。 好了，思路知道了——計算所有連續波谷波峰的差值之和。需要遍歷求得所有波谷波峰的值嗎？我最開始還真是這么想的，看了 soulmachine 的題解才發現原來可以把數組看成時間序列，只需要計算相鄰序列的差值即可，只累加大于0的差值。 ### Python ~~~ class Solution: """ @param prices: Given an integer array @return: Maximum profit """ def maxProfit(self, prices): if prices is None or len(prices) <= 1: return 0 profit = 0 for i in xrange(1, len(prices)): diff = prices[i] - prices[i - 1] if diff > 0: profit += diff return profit ~~~ ### C++ ~~~ class Solution { public: /** * @param prices: Given an integer array * @return: Maximum profit */ int maxProfit(vector<int> &prices) { if (prices.size() <= 1) return 0; int profit = 0; for (int i = 1; i < prices.size(); ++i) { int diff = prices[i] - prices[i - 1]; if (diff > 0) profit += diff; } return profit; } }; ~~~ ### Java ~~~ class Solution { /** * @param prices: Given an integer array * @return: Maximum profit */ public int maxProfit(int[] prices) { if (prices == null || prices.length <= 1) return 0; int profit = 0; for (int i = 1; i < prices.length; i++) { int diff = prices[i] - prices[i - 1]; if (diff > 0) profit += diff; } return profit; } }; ~~~ ### 源碼分析 核心在于將多個波谷波峰的差值之和的計算轉化為相鄰序列的差值，故 i 從1開始算起。 ### 復雜度分析 遍歷一次原數組，時間復雜度為 O(n)O(n)O(n), 用了幾個額外變量，空間復雜度為 O(1)O(1)O(1). ### Reference - soulmachine 的賣股票系列