題目描述
給定一個(gè)數(shù)組 prices ，其中 prices[i] 是一支給定股票第 i 天的價(jià)格。
設(shè)計(jì)一個(gè)算法來計(jì)算你所能獲取的最大利潤列林。你可以盡可能地完成更多的交易（多次買賣一支股票）。
注意：你不能同時(shí)參與多筆交易（你必須在再次購買前出售掉之前的股票）马胧。
示例
輸入: prices = [7,1,5,3,6,4]
輸出: 7
解釋: 在第 2 天（股票價(jià)格 = 1）的時(shí)候買入，在第 3 天（股票價(jià)格 = 5）的時(shí)候賣出, 這筆交易所能獲得利潤 = 5-1 = 4 衔峰。
隨后佩脊，在第 4 天（股票價(jià)格 = 3）的時(shí)候買入蛙粘，在第 5 天（股票價(jià)格 = 6）的時(shí)候賣出, 這筆交易所能獲得利潤 = 6-3 = 3 。
題目解析：
買賣股票就是低買高賣威彰，才能是利潤最大化出牧。這里可以進(jìn)行多次交易就意味著可以進(jìn)行多次交易，那么題目就可以轉(zhuǎn)換為歇盼，數(shù)組中有多少個(gè)單調(diào)遞增區(qū)間舔痕。利潤就是這些單調(diào)區(qū)間的最小值和最大值的差之和。
代碼
int maxProfit(vector<int>& prices) {
int result = 0;
int index = 0;
while (index < prices.size()) {
// 以index為開始豹缀，end為結(jié)束
int end = index + 1;
while (end < prices.size() && prices[end] > prices[end-1]) {
/// 找單調(diào)遞增區(qū)間
++end;
}
// end - 1才是單調(diào)增長區(qū)間結(jié)尾
if (prices[end-1] <= prices[index]) {
// 利潤 <= 0不考慮
++index;
} else {
// 計(jì)算單調(diào)區(qū)間利潤
result += prices[end-1] - prices[index];
index = end;
}
}
return result;
}
