买卖股票的最好时机(一)

描述

假设你有一个数组prices    
    
    
，长度为n


     


     


     ，其中prices[i]是股票在第i天的价格
 




 




 



，请根据这个价格数组   

   

   

，返回买卖股票能获得的最大收益 1.你可以买入一次股票和卖出一次股票 

     

     

    ，并非每天都可以买入或卖出一次

  




  




  


，总共只能买入和卖出一次  


  


  


，且买入必须在卖出的前面的某一天 2.如果不能获取到任何利润  
     
     
   ，请返回0 3.假设买入卖出均无手续费

解法一：暴力(常规大循环解决)

思路步骤：

最显而易见的解法


   




   




   

，当然可能并不是最优的解法 声明变量ans=0存放最终答案 两层for循环 



 



 



，分别找到数组中最大的差值               ，表示利润最大化 比较并更新ans的值 返回ans即为答案

代码

int ans = 0; for (int i = 0; i < prices.length; i++) { for (int j = i+1; j < prices.length; j++) { if (prices[j] - prices[i] > ans) { ans = prices[j] - prices[i]; } } } return ans;

解法二：关于解法一的优化：贪心算法

思路

我们假设自己购买股票



    




    




    
，为了达到利润最大化














，必然会挑一个历史最低点进行买入, 声明最低价格minPrices 那么在第i天卖出的股票的利润就是Prices[i]-minPrices 一趟遍历记录最低点即可

代码

package esay.JZ63买卖股票的最好时机1; public class Solution { /** * @param prices int整型一维数组 * @return int整型 */ public int maxProfit(int[] prices) { // write code here //1    
    
    
、暴力算法 /*int ans = 0; for (int i = 0; i < prices.length; i++) { for (int j = i+1; j < prices.length; j++) { if (prices[j] - prices[i] > ans) { ans = prices[j] - prices[i]; } } } return ans;*/ //2     


     


     


、贪心算法 int minPrice = Integer.MAX_VALUE; int ans = 0; for (int i = 0; i < prices.length; i++) { if (minPrice > prices[i]) { minPrice = prices[i]; } else if (prices[i] - minPrice > ans) { ans = prices[i] - minPrice; } } return ans; } }