题目描述
假设有一个数组，它的第i个元素是一个给定的股票在第i天的价格。设计一个算法来找到最大的利润。你可以完成尽可能多的交易(多次买卖股票)。然而,你不能同时参与多个交易(你必须在再次购买前出售股票)。
思路
贪心。
一开始认为买卖点都在头部，向后遍历
- 当出现卖点时，更新卖点和当前利润
- 未出现卖点，将当前利润累加到总利润中，并将买点指向当前点（完成了一次交易，为下次交易做准备）
即，只要发生利润A > 利润B，就卖掉利润A，开始下一次交易，这样每次操作都保证了利润的最大化，同时还为下一次交易做了准备
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| public int maxProfit(int[] prices) {
int res = 0;
int sell = 0;
int buy = 0;
int tmpMax = 0; // 当前这笔交易的最大利润
for(int i = 1; i < prices.length; i++) {
if((prices[i] - prices[buy] >= tmpMax)) { // 当前交易出现更好的卖点，更新
tmpMax = prices[i] - prices[buy];
sell = i;
if(i == prices.length-1) { // 如果是最后一个交易日，卖出股票
res += tmpMax;
}
}else { // 当前交易完成，为下一次交易做准备
res += tmpMax;
buy = i;
tmpMax = 0;
}
}
return res;
}
|
考察点