题解 | #买卖股票的最好时机(一)#

import java.util.*;


public class Solution {
    /**
     * 
     * @param prices int整型一维数组 
     * @return int整型
     */
    public int maxProfit (int[] prices) {
        if(prices.length==1){
            return 0;
        }
        // write code here
        //表示第几天买入第几天卖出的最收益
        int dp[][]=new int[prices.length][prices.length];
	  //代表第1天买入第二天卖出的收益
        dp[0][1]=prices[1]-prices[0];
        for(int i=0;i<prices.length-1;i++){
            for(int j=i+1;j<prices.length;j++){
			  //第i天买入第j天卖出的收益为前一天最大收益与今天卖出最大收益的最大值
                dp[i][j]=Math.max(dp[i][j-1],prices[j]-prices[i]);
                
            }
        }
	  //找出最大值
        int max=0;
        for(int i=0;i<prices.length;i++){
            for(int j=0;j<prices.length;j++){
                if(dp[i][j]>max){
                    max=dp[i][j];
                }
            }
        }

        return max;
    }
}