题目

链接：

Level: Easy

Discription:

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 (i.e., buy one and sell one share of the stock multiple times).

Example 1:

Input: [7,1,5,3,6,4]Output: 7Explanation: Buy on day 2 (price = 1) and sell on day 3 (price = 5), profit = 5-1 = 4.             Then buy on day 4 (price = 3) and sell on day 5 (price = 6), profit = 6-3 = 3.

Note:

• You may not engage in multiple transactions at the same time (i.e., you must sell the stock before you buy again).

代码1

class Solution {public:    int maxProfit(vector
    
     & prices) {        int buy=-1,sell=-1,profit=0;        for(int i=0;i
     
      =prices[i])                    buy=prices[i];                else if(buy
      
       =sell)                    sell = prices[i];                else                {                    profit+=sell-buy;                    sell=-1;                    buy=prices[i];                }            }            }        if(sell!=-1)            profit+=sell-buy;        return profit;    }};
      
     
    

代码2

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

思考

• 算法时间复杂度为O(n),空间复杂度为O(1)。
• 代码1是记录好每次的低位买进点和高位卖出点，再计算profit。而代码二是抓住了题目的特征，只要后面一个价格比前面高我就可以算上这个差值作为利润。速度更快。这题奇怪的是股票价格还有零的。