pic

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).

分析

题意是：现有一个整形数组，数组的第i个元素表示第i天某只股票的股价；在允许多次交易（在买前必须卖出手里所有的股票）的前提下，求最大收益。

这道题目是“Best Time to Buy and Sell Stock”的扩展，但是更简单，只因题目已经设置了限制条件：在买前必须卖出手里有的股票。要获得最大收益，只需买入最多次的股票，而每次卖出都希望能收益：可以看出这个题目符合贪心策略。

Code

class Solution {
public:
    /* 
     * 这道题目比较简单，只因题目已经设置了限制条件：在买前必须卖出手里有的股票
     * 要获得最大收益，只需买入最多次的股票，而每次卖出都希望能收益
     * 可以看出这个题目符合贪心策略
     * */
    int maxProfit(vector<int> &prices) {
        // IMPORTANT: Please reset any member data you declared, as
        // the same Solution instance will be reused for each test case.
        if( prices.size() < 2)
            return 0;
        int sumProfit = 0;
        int temp = 0;
        for( int i = 0; i < prices.size() - 1; i++)
        {
            temp = prices[i+1] - prices[i];
            if( temp > 0 )
                sumProfit += temp;
        }
        return sumProfit;
    }
};

pic