Best Time to Buy and Sell Stock

Key point is to keep track of the smaller "buying price" and update profit when current price can make more money if sold out. DP is usually applied when we need to find out some optimized value, like max or min. profits[i] means max profit by ith day.

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

code ganker's post about this question: http://blog.csdn.net/linhuanmars/article/details/23162793
His answer is much better, with only O(1) space. And the idea is simpler and more general. Key point he proposes is local optimization and global optimization.

A better and general explanation can be found in the 3rd version of this problem: http://blog.csdn.net/linhuanmars/article/details/23236995