75.买卖股票得最佳时期

示例 1：

输入：[7,1,5,3,6,4]输出：5解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。 注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。

示例 2：

输入：prices = [7,6,4,3,1]输出：0解释：在这种情况下, 没有交易完成, 所以最大利润为 0。

int min(int a,int b){ return a<b?a:b; } int max(int a,int b){ return a>b?a:b; } int maxProfit(int* prices, int pricesSize) { if(pricesSize<=1) return 0; int min_price = prices[0]; int profit = 0;//dp[0] for(int i=1;i<=pricesSize-1;i++){ min_price=min(min_price,prices[i]); profit = max(profit,prices[i]-min_price);//dp[1] = max(dp[0],price[1]-minprice) } return profit; } ///dp[i] 表示前 i 天的最大利润，因为我们始终要使利润最大化，则： ///dp[i]=max(dp[i−1],prices[i]−minprice)