Say you have an array for which the ith element is the price of a given stock on day i.
If you were only permitted to complete at most one transaction (ie, buy one and sell one share of the stock), design an algorithm to find the maximum profit.
Example 1:
Input: [7, 1, 5, 3, 6, 4]
Output: 5
max. difference = 6-1 = 5 (not 7-1 = 6, as selling price needs to be larger than buying price)
Example 2:
Input: [7, 6, 4, 3, 1]
Output: 0
In this case, no transaction is done, i.e. max profit = 0.
讀題
題目的意思就是給你一個數(shù)組篓吁，第i個元素表示第i天貨物的價格铭污，假定只允許進行一次交易，求最大的利潤
解題思路
要想獲得最大的利潤就是要低買高賣惋嚎，也就是以最低的價格買入以最高的價格賣出，還要明確的是賣一定是在買之后嘲驾。
可能會想到用兩層循環(huán)解決這樣的問題展鸡，但是會存在超時的情況，再者如果一個數(shù)組是遞增的九昧，那么你外層循環(huán)是沒有意義的，如果一個數(shù)組是遞減的毕匀，那么也不存在獲利的情況铸鹰，所有用兩層循環(huán)去解決是不現(xiàn)實的。
我們要盡量使用O(n)時間復(fù)雜度去完成這樣一個任務(wù)
我們看這張圖片期揪，假定我們在a點買入掉奄，在b點賣出，那么我們在[a,b]之間就實現(xiàn)了當前的利潤最大凤薛，那么如果我們在a點買入姓建，c點賣出就是虧了，如果我們在c點之后的某時刻（價格高于a點的價格）賣出缤苫，這個時候在c點買入肯定要比在a點買入的利潤大速兔，明白了這一點就好辦了，其實我們的任務(wù)就是找最低買入價活玲！
代碼演示
package com.xiaoysec;
public class Solution121 {
public int maxProfit(int[] prices){
if(prices.length <= 1)
return 0;
//當前的最低買入價
int minPrice = prices[0];
int maxPrice = 0;
//O(n)的時間復(fù)雜度
for(int i=1;i<prices.length;i++){
//如果當前的價格比最低價低就作為買入價
if(prices[i]<minPrice)
minPrice = prices[i];
else
//當前的價格高于買入價（最低價）就計算利潤并與最大利潤比較
maxPrice = Math.max(maxPrice, prices[i]-minPrice);
}
return maxPrice;
}
public static void main(String[] args){
int[] prices = {7, 1, 5, 3, 6, 4};
Solution121 solution = new Solution121();
int maxprofix = solution.maxProfit(prices);
System.out.println(maxprofix);
}
}
