leetcode122

public class Solution {
    public int MaxProfit(int[] prices) {
        var list = new List<KeyValuePair<int, int>>();
            //记录所有的极大值和极小值

            if (prices.Length <= 1)
            {
                return 0;
            }
            else if (prices.Length == 2)
            {
                return prices[1] - prices[0] > 0 ? prices[1] - prices[0] : 0;
            }
            else
            {
                for (int i = 1; i < prices.Length - 1; i++)
                {
                    var last = prices[i - 1];
                    var cur = prices[i];
                    var next = prices[i + 1];
                    if ((last < cur && cur >= next) || (last <= cur && cur > next))
                    {
                        list.Add(new KeyValuePair<int, int>(i, 1));//记录极大值
                    }
                    if ((last > cur && cur <= next) || (last >= cur && cur < next))
                    {
                        list.Add(new KeyValuePair<int, int>(i, -1));//记录极小值
                    }
                }

                var firstnode = list.FirstOrDefault();
                var lastnode = list.LastOrDefault();

                if (firstnode.Value == 1)
                {
                    list.Add(new KeyValuePair<int, int>(0, -1));//第一个坐标当做极小值
                }
                else if (firstnode.Value == -1)
                {
                    list.Add(new KeyValuePair<int, int>(0, 1));//第一个坐标当做极大值
                }
                else
                {
                    if (prices[0] < prices[prices.Length - 1])
                    {
                        list.Add(new KeyValuePair<int, int>(0, -1));//第一个坐标当做极小值                        
                    }
                    else
                    {
                        list.Add(new KeyValuePair<int, int>(0, 1));//第一个坐标当做极大值                        
                    }
                }

                if (lastnode.Value == 1)
                {
                    list.Add(new KeyValuePair<int, int>(prices.Length - 1, -1));//最后一个坐标当做极小值
                }
                else if (lastnode.Value == -1)
                {
                    list.Add(new KeyValuePair<int, int>(prices.Length - 1, 1));//最后一个坐标当做极大值
                }
                else
                {
                    if (prices[0] < prices[prices.Length - 1])
                    {
                        list.Add(new KeyValuePair<int, int>(prices.Length - 1, 1));//最后一个坐标当做极大值
                    }
                    else
                    {
                        list.Add(new KeyValuePair<int, int>(prices.Length - 1, 1));//最后一个坐标当做极大值
                    }
                }

                list = list.OrderBy(x => x.Key).ToList();

                var sum = 0;

                var min = -1;
                var max = -1;

                int pair = 0;
                for (int i = 0; i < list.Count; i++)
                {
                    if (list[i].Value == -1)
                    {
                        min = list[i].Key;
                        pair = 1;
                    }
                    if (pair == 1 && list[i].Value == 1)
                    {
                        max = list[i].Key;
                        pair += 2;

                    }
                    if (pair == 3)
                    {
                        sum += prices[max] - prices[min];
                        pair = 0;
                    }
                }
                return sum;
            }
    }
}

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

上面这种方法比较复杂，还有一种更简单直接的方法

public class Solution {
    public int MaxProfit(int[] prices) {
        int total = 0;
        for (int i=0; i< prices.Length-1; i++) {
            if (prices[i+1]>prices[i]) total += prices[i+1]-prices[i];
        }
    
        return total;
    }
}

只要后面的比前面的多，就进行一次买卖。计算的结果是一样的，但是与题意并不相符。题意要求在同一时间不能既买又卖。也就是要尽量减少交易次数。

所以严格来讲，第二种方法并不是是正确的解答，虽然答案一样。

时隔一年半的时间，在学习了贪婪算法的思想后，重新解此题，明白了上面的思想。只要下一次比上一次的金额高，就进行一次累计，C++程序如下：

int maxProfit(vector<int>& prices) {
    int sum = 0;
    if (prices.size() > 1)
    {
        int lastP = prices[0];
        for (int i = 1; i < prices.size(); i++)
        {
            int p = prices[i];
            if (p > lastP)
            {
                sum += p - lastP;
            }
            lastP = p;
        }
    }
    return sum;
}

补充一个python的实现：

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        n = len(prices)
        sums = 0
        for i in range(1,n):
            if prices[i] > prices[i-1]:
                sums += prices[i] - prices[i-1]
        return sums