### 121. Best Time to Buy and Sell Stock

题目:
<https://leetcode.com/problems/best-time-to-buy-and-sell-stock/>


难度:

Easy


思路

All the straight forward solution should work, but if the interviewer twists the question slightly 
by giving the difference array of prices, Ex: for ```{1, 7, 4, 11}```, if he gives ```{0, 6, -3, 7}```, 
you might end up being confused.

Here, the logic is to calculate the difference ```(maxCur += prices[i] - prices[i-1])```
of the original array, and find a contiguous subarray giving maximum profit. 
If the difference falls below ```0```, reset it to zero.

参考[Maximum subarray problem](https://en.wikipedia.org/wiki/Maximum_subarray_problem), 
[Kadane's Algorithm](https://discuss.leetcode.com/topic/19853/kadane-s-algorithm-since-no-one-has-mentioned-about-this-so-far-in-case-if-interviewer-twists-the-input)


```
Why maxCur = Math.max(0, maxCur += prices[i] - prices[i-1]); ?

Well, we can assume opt(i) as the max Profit you will get if you sell the stock at day i;

We now face two situations:

We hold a stock at day i, which means opt(i) = opt(i - 1) - prices[i - 1] + prices[i] (max Profit you can get if you sell stock at day(i-1) - money you lose if you buy the stock at day (i-1) + money you gain if you sell the stock at day i.

We do not hold a stock at day i, which means we cannot sell any stock at day i. In this case, money we can get at day i is 0;

opt(i) is the best case of 1 and 2.

So, opt(i) = Max{opt(i - 1) - prices[i - 1] + prices[i], 0}
```


```python
class Solution(object):
    def maxProfit(self, prices):
        """
        :type prices: List[int]
        :rtype: int
        """
        if not prices:
            return 0
        res, max_cur = 0, 0
        for i in range(1, len(prices)):
            max_cur = max(0, max_cur+prices[i]-prices[i-1])
            res = max(res, max_cur)
        return res
```