https://leetcode.com/problems/best-time-to-buy-and-sell-stock/

給定一個數(shù)組，其中數(shù)組的第 i 個元素表示第 i 天的股票價格，你可以選擇在其中一天買股票，然后再后面的某一天賣掉股票，求最大收益。（股票必須要先買才能賣）這里只能買一次，也只能賣一次
------
Example 1:
Input: [7,1,5,3,6,4]
Output: 5
Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5.
Not 7-1 = 6, as selling price needs to be larger than buying price.
----------------------
Example 2:
Input: [7,6,4,3,1]
Output: 0
Explanation: In this case, no transaction is done, i.e. max profit = 0.

分析

該題與 子數(shù)組的最大和 相似 https://leetcode.com/problems/maximum-subarray/ ，其解答參見 http://www.itdecent.cn/p/98676b3baf2c

• 子數(shù)組的最大和 是求 nums[i] + .... + nums[j] 的最大值
• 而這里買股票和賣股票是求 num[j] - num[i] 的最大值，而
  nums[j] - nums[i] = (nums[j] - nums[j-1]) + (nums[j-1] - nums[j-2]) + ..... + (nums[i+1] - nums[i])
• 所以可以將 子數(shù)組的最大和 中的nums[i] 替代為 nums[i+1] - nums[i]

maxhere 記錄的是當(dāng)前購買和賣出的利潤，如果利潤小于0，就要重新購買股票，即將maxhere置0；
同時用一個maxsofar記錄每次購買和賣出的利潤，取其最大值

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int maxhere = 0, maxsofar = 0;
        for (int i=1; i<prices.size(); ++i)
        {
            maxhere = (maxhere + prices[i]-prices[i-1])> 0?(maxhere + prices[i]-prices[i-1]):0;
            maxsofar = maxhere > maxsofar ? maxhere : maxsofar;
        }
        return maxsofar;
    }
};