贪心算法
给定一个数组 prices ，其中 prices[i] 是一支给定股票第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
由题可知，求最大利润，可以想到贪心算法，贪心算法的思想是将问题分解成一个个小问题，然后求得局部最优解
而此题可以分解为价格递增天数的总和，即在递增序列之后遇到下降点，就将之前的递增求差，最后求和。
举例，上图可知，1->5为递增，而5->3下降，所以将5-1的差作为最终利润的一部分
使用双向队列deque解题。
class Solution {
public int maxProfit(int[] prices) {
Deque<Integer> deque=new LinkedList<Integer>();
int length=prices.length;
int maxProfit=0;
for(int i=0;i<length;i++){
if(deque.isEmpty()){
deque.add(prices[i]);
}
else if(deque.peekLast()<prices[i]){
deque.add(prices[i]);
}
else{
maxProfit+=deque.peekLast()-deque.peekFirst();
deque.clear();
deque.add(prices[i]);
}
}
if(!deque.isEmpty()&&(deque.peekLast()>deque.peekFirst()))
maxProfit+=deque.peekLast()-deque.peekFirst();
return maxProfit;
}
}
这是最初想的，虽然通过了，但太累赘了，所以看了看别人的代码学习了一下。
class Solution {
public int maxProfit(int[] prices) {
int ans = 0;
int n = prices.length;
for (int i = 1; i < n; ++i) {
ans += Math.max(0, prices[i] - prices[i - 1]);
}
return ans;
}
}