（java版剑指offer）JZ63 买卖股票的最好时机(一)(三种方法：暴力破解+贪心算法)

//方法一：暴力破解
//时间复杂度：n^2
//空间复杂度：1
import java.util.*;


public class Solution {
    /**
     * 
     * @param prices int整型一维数组 
     * @return int整型
     */
    public int maxProfit (int[] prices) {
        // write code here
        //暴力破解：
        //分析：双重循环
        //外循环：买股票
        //内循环：卖股票，买卖股票做差，找出最大值
        int max = 0;
        int profit = 0;
        
        for(int i=0; i<prices.length; i++)
           for(int j=i+1; j<prices.length; j++){
               profit = prices[j] - prices[i];
               max = Math.max(max, profit);
           }
        return max;
    }
}

//方法二：暴力+贪心
//时间复杂度：n
//空间复杂度：1
import java.util.*;
public class Solution {
    /**
     * 
     * @param prices int整型一维数组 
     * @return int整型
     */
    public int maxProfit (int[] prices) {
        // write code here
        //暴力破解优化（贪心算法）：
        //分析：单循环
        //先找最低价格买入，再卖出，找差值最大值
        int max = 0;
        //如果定义为：int minPrice = Integer.MAX_VALUE;
        //那么循环初始条件：int i = 0;
        int minPrice = prices[0];
        
        for(int i=1; i<prices.length; i++){
            //找价格最低，是价格最低，就交换
            if(prices[i] < minPrice){
                minPrice = prices[i];
            }
            //没找到价格最低，就将当天的价格减去之前买入的最低价作为临时最大值
            else{
                max = Math.max((prices[i] - minPrice), max);
            }
        }
        return max;
    }
}