買賣股票的最好時機(一)

描述

假設你有一個數組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;
    }
}