Best Time to Buy and Sell Stock

leetcode第121题，简单题，要求寻找一个最好的买入卖出时机，使得两个数字相差最大，即获益最多。 题目提示是动态规划，但实际好像没那么复杂。首先，一种最直接的思路，两边循环搞定，外循环遍历买入时机，内循环遍历卖出时机。 能不能简化一下呢，假设只用一次循环，就是遍历卖出时机，什么时候卖出呢，当然是与之前的所有值中最小值差距最大的时候，这就很明显了，我们可以一边遍历卖出点，一遍记录卖出点之前的最小值，这样就可以求出最大收益了。

public class Solution { public int maxProfit(int[] prices) { if (prices == null || prices.length == 0){ return 0; } int min = prices[0]; int len = prices.length; int profit = 0; for(int i = 0;i < len;i++){ min = Math.min(min, prices[i]); profit = Math.max(prices[i]-min, profit); } return profit; } }