LeetCode122-Best Time to Buy and Sell Stock II

题目

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 (ie, buy one and sell one share of the stock multiple times). However, you may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

分析

这次的股票题II不同于I,它允许多次买进 + 卖出,甚至在一天内!所以思路就已经非常清晰了,我们只要跟着时间的流逝(从头到尾遍历prices),只要发现有利润可以赚的时候就马上买进或卖出,比如[4, 5, 3, 6, 3, 7],发现4-5,3-6,3-7都可以产生利润,那么此时利润最大为1 + 3 + 4 = 8。也许可能有一点会有顾虑:比如prices[2] = 3时,为什么要在prices[3] = 6时卖出呢?为什么不能在prices[5] = 7时卖出呢,他们差距更大些啊?这就是因为我们可以多次买进卖出甚至当日,prices[5] = 7卖出的话相当于之前抱着prices[3] = 6的股不放,不卖出,仅管是赚到了6 – 3 = 3的这3,但却忽略了后面的低价3,不低买进prices[4] = 3,必将导致最后的涨幅缩减,只能多赚1不能多赚3。

那或许会说,假如是[4, 5, 6, 3, 7]的情况呢,4-5,5-6,3-7便是我们可以赚到的差价来源,在prices[1] = 5的时候照理说可以不用卖,再买,但为了统一代码,我们就直接卖5再买5了。

代码

public class Solution {
    public int maxProfit(int[] prices) {
        int profit = 0;
        for (int day = 1; day < prices.length; day++) {
            if (prices[day] > prices[day - 1])
                profit += prices[day] - prices[day - 1];
        }
        
        return profit;
    }
}

Leave a Comment.