leetcode122

public class Solution {

    public int MaxProfit(int[] prices) {

        var list = new List<KeyValuePair<int, int>>();

            //记录所有的极大值和极小值

            if (prices.Length <= )

            {

                return ;

            }

            else if (prices.Length == )

            {

                return prices[] - prices[] >  ? prices[] - prices[] : ;

            }

            else

            {

                for (int i = ; i < prices.Length - ; i++)

                {

                    var last = prices[i - ];

                    var cur = prices[i];

                    var next = prices[i + ];

                    if ((last < cur && cur >= next) || (last <= cur && cur > next))

                    {

                        list.Add(new KeyValuePair<int, int>(i, ));//记录极大值

                    }

                    if ((last > cur && cur <= next) || (last >= cur && cur < next))

                    {

                        list.Add(new KeyValuePair<int, int>(i, -));//记录极小值

                    }

                }

                var firstnode = list.FirstOrDefault();

                var lastnode = list.LastOrDefault();

                if (firstnode.Value == )

                {

                    list.Add(new KeyValuePair<int, int>(, -));//第一个坐标当做极小值

                }

                else if (firstnode.Value == -)

                {

                    list.Add(new KeyValuePair<int, int>(, ));//第一个坐标当做极大值

                }

                else

                {

                    if (prices[] < prices[prices.Length - ])

                    {

                        list.Add(new KeyValuePair<int, int>(, -));//第一个坐标当做极小值

                    }

                    else

                    {

                        list.Add(new KeyValuePair<int, int>(, ));//第一个坐标当做极大值

                    }

                }

                if (lastnode.Value == )

                {

                    list.Add(new KeyValuePair<int, int>(prices.Length - , -));//最后一个坐标当做极小值

                }

                else if (lastnode.Value == -)

                {

                    list.Add(new KeyValuePair<int, int>(prices.Length - , ));//最后一个坐标当做极大值

                }

                else

                {

                    if (prices[] < prices[prices.Length - ])

                    {

                        list.Add(new KeyValuePair<int, int>(prices.Length - , ));//最后一个坐标当做极大值

                    }

                    else

                    {

                        list.Add(new KeyValuePair<int, int>(prices.Length - , ));//最后一个坐标当做极大值

                    }

                }

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

                var sum = ;

                var min = -;

                var max = -;

                int pair = ;

                for (int i = ; i < list.Count; i++)

                {

                    if (list[i].Value == -)

                    {

                        min = list[i].Key;

                        pair = ;

                    }

                    if (pair ==  && list[i].Value == )

                    {

                        max = list[i].Key;

                        pair += ;

                    }

                    if (pair == )

                    {

                        sum += prices[max] - prices[min];

                        pair = ;

                    }

                }

                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 = ;

        for (int i=; i< prices.Length-; i++) {

            if (prices[i+]>prices[i]) total += prices[i+]-prices[i];

        }

        return total;

    }

}

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

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

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

int maxProfit(vector<int>& prices) {

    int sum = ;

    if (prices.size() > )

    {

        int lastP = prices[];

        for (int i = ; 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 =

         for i in range(,n):

             if prices[i] > prices[i-]:

                 sums += prices[i] - prices[i-]

         return sums

巴特西

leetcode122

最新文章

热门文章