leetcode-122-Best-Time-to-Buy-and-Sell-Stock-II

发表于   |  

描述

Say you have an array for which the $i^{th}$ element is the price of a given stock on day i.

If you were only permitted to complete at most one transaction (ie, buy one and sell one share of the stock), design an algorithm to find the maximum profit.

分析

与 leetcode-121-Best-Time-to-Buy-and-Sell-Stock 类似，区别是上一道题只买卖一次股票，这道题可以买卖无限次。要求股票最佳收益，我们可以想象一张股票 k 线图，把每一段上涨的红线加起来即可。时间复杂度是 $O(n)$

解决方案1(C++)

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int result = 0, n = prices.size();
        for (int i = 0; i < n-1; i++) {
            if (prices[i] < prices[i+1]) {
                result += (prices[i+1] - prices[i]);
            }
        }
        return result;
    }
};

解决方案2(Java)

1
2
3
4
5
6
7
8
9
10
11
class Solution {
    public int maxProfit(int[] prices) {
        int result = 0, n = prices.length;
        for (int i=0; i < n-1; i++) {
            if (prices[i] < prices[i+1]) {
                result += (prices[i+1]-prices[i]);                
            }
        }
        return result;
    }
}

解决方案3(Golang)

1
2
3
4
5
6
7
8
9
func maxProfit(prices []int) int {
    result := 0
    for i:= 0; i < len(prices)-1; i++ {
        if prices[i+1] > prices[i] {
            result += (prices[i+1]-prices[i])
        }
    }
    return result
}

相关问题

题目来源