今日简单题：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock/
看题要求最大差值，知道是动态规划，但是规划方程只能推导出：
用暴力法可以通过自测用例，但数据量变大的时候，会提示超过时间限制，需要优化时间复杂度。
但是答案中的解释存在问题，说必须找到最低点后再购买的假设是错误的，因为最低点可能是最后一个值，或者差值较小，比如[10,12,7,8,3]，这种情况下最大差值是2；
优化后的思路应该是遍历一遍，把最小值和后面数的差值存起来，遇到大的取大的。
最后贴2种解法：
1.暴力法代码如下：
class Solution {
public int maxProfit(int[] prices) {
int ans = 0;
for (int i = 0; i< prices.length-1; i++) {
for (int j = i+1;j<prices.length;j++) {
if (prices[j]>prices[i]) {
ans = Math.max(ans,prices[j]-prices[i]);
}
}
}
return ans;
}
}
2.优化时间复杂度后：
class Solution {
public int maxProfit(int[] prices) {
int min = Integer.MAX_VALUE;
int max = 0;
for (int i = 0; i< prices.length; i++) {
if (min > prices[i]) {
min = prices[i];
}
else if (max < prices[i]-min) {
max = prices[i]-min;
}
}
return max;
}
}
