每日算法题之买卖股票的最好时机(一)

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

假设你有一个数组prices，长度为n，其中prices[i]是股票在第i天的价格，请根据这个价格数组，返回买卖股票能获得的最大收益1.你可以买入一次股票和卖出一次股票，并非每天都可以买入或卖出一次，总共只能买入和卖出一次，且买入必须在卖出的前面的某一天2.如果不能获取到任何利润，请返回03.假设买入卖出均无手续费

解法一：暴力(常规大循环解决)思路步骤：

最显而易见的解法，当然可能并不是最优的解法声明变量ans=0存放最终答案两层for循环，分别找到数组中最大的差值，表示利润最大化比较并更新ans的值返回ans即为答案

代码

int ans = 0;for (int i = 0; i < prices.length; i++) {    for (int j = i+1; j  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  ans) {                    ans = prices[j] - prices[i];                }            }        }        return ans;*/        //2、贪心算法        int minPrice = Integer.MAX_VALUE;        int ans = 0;        for (int i = 0; i  prices[i]) {                minPrice = prices[i];            } else if (prices[i] - minPrice > ans) {                ans = prices[i] - minPrice;            }        }        return ans;    }}