給定一個數組 prices ，它的第 i 個元素 prices[i] 表示一支給定股票第 i 天的價格。

你只能選擇 某一天 買入這只股票，并選擇在 未來的某一個不同的日子 賣出該股票。設計一個算法來計算你所能獲取的最大利潤。

返回你可以從這筆交易中獲取的最大利潤。如果你不能獲取任何利潤，返回 0 。

代碼一：暴力法

class Solution {public int maxProfit(int[] prices) {int res = 0;for(int buy = 0;buy<prices.length-1;buy++){for(int sale = buy+1;sale<prices.length;sale++){int temp = prices[sale]-prices[buy];if(temp>res){res = temp;}}}return res;}
}

時間過長，無法通過

代碼二：
線性規劃，arr[i]代表以第i-1天買進能獲得的最大利潤，那么arr[i]和arr[i+1]是有關系的，我們從最后一天開始倒著推，因為最后一天利潤一定是0。代碼二和最大子序和題目思路一樣

public class Solution {public int maxProfit(int prices[]) {if(prices.length<2){return 0;}int[] arr = new int[prices.length];int maxprofit = 0;for(int i = prices.length-2;i>=0;i--){int temp = prices[i+1]-prices[i];if(prices[i]<prices[i+1]){arr[i] = arr[i+1]+temp;}else{arr[i] = arr[i+1]+temp>=0?arr[i+1]+temp:0;}maxprofit = Math.max(maxprofit,arr[i]);}return maxprofit;}
}