题目链接

结果

代码实现：

class Solution {
    public int maxProfit(int[] prices) {
       if(prices==null||prices.length<=1){
            return 0;
        }
        int last = prices[0];
        int now;
        int count=0;
        int len = prices.length;
        for(int i = 1;i < len;i++){
            now = prices[i];
            if(now >= last){
                count += now - last;
            }
            last = now;
        }
        return count;
    }
}

过程

代码实现很简单，通过一次遍历，时间复杂度为O(n)即可完成，具体思路是，遍历数组，将价格走势分段，分段计入利润（每段是一天），记录上一个index的元素值，进行比较，如果当前值比前一个元素的值大的话那么就计入利润总数，如果当前值比前一个元素的值小的话，那么就不计入利润总数。可以抽象为记录前一个的值是假设买入的值（last），当前值是假设买入后卖出的值（now），如果now<last那么就不能买，所以这部分不计入利润值，如果now>=last说明可以卖出，那么就计入利润总数。这里面把连续上涨的周期抽象为连续买入卖出操作，比如[1,2,3]，就是第一天买入，第二天卖出，第二天再买入，第三天再卖出，如果变成[1,2,1]的话，就是第一天买入，第二天卖出，第二天假设买入，第三天发现赔钱，所以第二天不买入，效果与算连续周期的一样（[1,2,3]的利润是3-1=2，即第一天买入，第三天卖出）。