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).
Subscribe to see which companies asked this question.
假設有一個數(shù)組岩调，它的第i個元素是一個給定的股票在第i天的價格。設計一個算法來找到最大的利潤。你可以完成盡可能多的交易(多次買賣股票)。然而,你不能同時參與多個交易(你必須在再次購買前出售股票)。
樣例
給出一個數(shù)組樣例[2,1,2,0,1], 返回 2
SOLUTION
Approach #1 (Simple One Pass) 貪心法
很簡單扯饶，既然可以進行任意次的交易，那么我們就將所有前一天比后一天價格低的都進行交易，因為只有這樣毫目，才會增加收益，所以我們進行一次遍歷之后诲侮，就可以求出的最大收益值镀虐。
我們可以看到 A+B+C就等于D
class Solution {
public int maxProfit(int[] prices) {
int maxprofit = 0;
for (int i = 1; i < prices.length; i++) {
if (prices[i] > prices[i - 1])
maxprofit += prices[i] - prices[i - 1];
}
return maxprofit;
}
}
Complexity Analysis
- Time complexity : O(n)O(n). Single pass.
- Space complexity: O(1)O(1). Constant space needed.
Approach #2 (Peak Valley Approach)
假設給定的數(shù)組是：
[7, 1, 5, 3, 6, 4].
我們觀察這個圖，可以得出我們的收益是由連續(xù)的山頂山谷組成的
這里最關鍵的點就是我們找到一個山谷就要立即跟他最近的山頂求和沟绪，否則如何越到下一個山頂求和刮便，就不是最大的收益了。正如圖中所示
class Solution {
public int maxProfit(int[] prices) {
int i = 0;
int valley = prices[0];
int peak = prices[0];
int maxprofit = 0;
while (i < prices.length - 1) {
while (i < prices.length - 1 && prices[i] >= prices[i + 1])
i++;
valley = prices[i];
while (i < prices.length - 1 && prices[i] <= prices[i + 1])
i++;
peak = prices[i];
maxprofit += peak - valley;
}
return maxprofit;
}
}
