連結
https://leetcode-cn.com/problems/gu-piao-de-zui-da-li-run-lcof/ 難度: #中等
題目
假設把某股票的價格按照時間先後順序存儲在數組中,請問買賣該股票一次可能獲得的最大利潤是多少?示例 1:
輸入: [7,1,5,3,6,4]
輸出: 5
解釋: 在第 2 天(股票價格 = 1)的時候買入,在第 5 天(股票價格 = 6)的時候賣出,最大利潤 = 6-1 = 5 。
注意利潤不能是 7-1 = 6, 因為賣出價格需要大于買入價格。
示例 2:
輸入: [7,6,4,3,1]
輸出: 0
解釋: 在這種情況下, 沒有交易完成, 是以最大利潤為 0。
限制:
0 <= 數組長度 <= 10^5
注意:本題與主站 121 題相同:https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock/
代碼架構
class Solution {
public int maxProfit(int[] prices) {
}
}
題目解析
解答思路1:
周遊數組,
分别把目前的元素作為買入時機,
把目前元素後面的元素依次作為賣出時機,
進而找到最大利潤。
解答思路2:
優化暴利解法,
在尋找第i天後賣出的最佳時機,
存在重複子問題,
優化後避免的重複尋找。
周遊數組,
從第i天開始買入prices[i],
則第i天後面的最大值prices[m]可以賣出,
取profit=Max(profit,prices[m]-prices[i]),
再計算第i+1天的買入prices[i+1],
則第i+1天後面的最大值prices[n]可以賣出,
取profit=Max(profit,prices[n]-prices[j]),
讨論兩次最大值prices的下标m和n,
如果m=n,則存在重複子問題,
不需要反複計算下标的最大值,
可以極大的優化暴利解法的性能,
是以需要記錄最大值所在的下标m,
可以知道第i到m-1天後面的最大值都是prices[m],
考慮數組[7,1,5,3,6,4]
對應下标[0,1,2,3,4,5]
第0到3次的最大值都是6,下标為4,
第4次由于自己本身是最大值,沒有比較的必要了,
後面如果還有其他值,
可以從第m+1個元素開始遞歸,
重複進行上述操作,
目前最大值前面的值都不需要在考慮了,
因為無論前m-1個元素多小,
後面的最大值已經是第m個元素了,
兩者的內插補點不可能再大了。
解答思路3:
周遊數組一遍,
在周遊第i天的時候,
找出到目前為止目前的最小值,
然後假設自己就是在那一天買的,
不需要确切知道是哪一天買的,
然後在第i天的時候,
計算賣出的利潤,
儲存利潤的最大值,
直到數組周遊完畢,
就能獲得最大的利潤,
不需要确切知道是哪一天賣的。
測試用例
package edu.yuwen.sowrd.d60.num63.solution;
import org.junit.jupiter.api.Assertions;
import org.junit.jupiter.api.Test;
import edu.yuwen.sowrd.d60.num63.sol5.Solution;
public class SolutionTest {
/**
* 示例 1:
* 輸入: [7,1,5,3,6,4]
* 輸出: 5
* 解釋: 在第 2 天(股票價格 = 1)的時候買入,在第 5 天(股票價格 = 6)的時候賣出,最大利潤 = 6-1 = 5 。
* 注意利潤不能是 7-1 = 6, 因為賣出價格需要大于買入價格。
*/
@Test
public void testCase1() {
Solution solution = new Solution();
int[] prices = { 7, 1, 5, 3, 6, 4 };
int res = solution.maxProfit(prices);
Assertions.assertEquals(5, res);
}
/**
* 示例 2:
* 輸入: [7,6,4,3,1]
* 輸出: 0
* 解釋: 在這種情況下, 沒有交易完成, 是以最大利潤為 0。
*/
@Test
public void testCase2() {
Solution solution = new Solution();
int[] prices = { 7, 6, 4, 3, 1 };
int res = solution.maxProfit(prices);
Assertions.assertEquals(0, res);
}
/**
* 輸入: [2,1,4]
* 輸出: 3
* 解釋: 在這種情況下, 沒有交易完成, 是以最大利潤為 0。
*/
@Test
public void testCase3() {
Solution solution = new Solution();
int[] prices = { 2, 1, 4 };
int res = solution.maxProfit(prices);
Assertions.assertEquals(3, res);
}
}
解答1
package edu.yuwen.sowrd.num63.sol1;
public class Solution {
public int maxProfit(int[] prices) {
if (prices == null || prices.length == 0) {
return 0;
}
// 初始化最大利潤為0
int max = 0;
// 買入時機,最後一天無法作為買入時機
for (int i = 0; i < prices.length - 1; i++) {
// 賣出時機
for (int j = i + 1; j < prices.length; j++) {
// 找出最大利潤
int profit = prices[j] - prices[i];
max = Math.max(max, profit);
}
}
return max;
}
}
解答2
package edu.yuwen.sowrd.num63.sol2;
public class Solution {
public int maxProfit(int[] prices) {
if (prices == null || prices.length == 0) {
return 0;
}
int profit = 0;
int maxIndex = -1;
// 第i天買入時機,最後一天無法買入
for (int i = 0; i < prices.length - 1; i++) {
// 最大值的時候,也無法買入
if (i == maxIndex) {
continue;
}
// i大于最大值的下标,則需要重新查找最大值
if (i > maxIndex) {
// 找到i+1到length-1的最大值的下标,左閉右開
maxIndex = findMax(prices, i + 1);
}
profit = Math.max(profit, prices[maxIndex] - prices[i]);
}
return profit;
}
private int findMax(int[] prices, int i) {
int max = Integer.MIN_VALUE;
int maxIndex = -1;
for (int m = i; m < prices.length; m++) {
// 找到最大值的下标,且如果有重複的最大值,取索引最大的
if (max <= prices[m]) {
max = prices[m];
maxIndex = m;
}
}
return maxIndex;
}
}
解答3
package edu.yuwen.sowrd.num63.sol3;
public class Solution {
public int maxProfit(int[] prices) {
if (prices == null || prices.length == 0) {
return 0;
}
int profit = 0;
int min = prices[0];
for (int i = 1; i < prices.length; i++) {
// 更新最小值,且買入當天不賣出
if (min > prices[i]) {
min = prices[i];
continue;
}
// 更新最大利潤
int newP = prices[i] - min;
if (profit < newP) {
profit = newP;
}
}
return profit;
}
}
解答4 推薦
package edu.yuwen.sowrd.num63.sol4;
public class Solution {
public int maxProfit(int[] prices) {
int cost = Integer.MAX_VALUE, profit = 0;
for (int price : prices) {
cost = Math.min(cost, price);
profit = Math.max(profit, price - cost);
}
return profit;
}
}
解答5
package edu.yuwen.sowrd.num63.sol5;
public class Solution {
public int maxProfit(int[] prices) {
if (prices == null || prices.length == 0) {
return 0;
}
int[] dp = new int[prices.length];
// 當天買入賣出利潤0
dp[0] = 0;
// 前i天的最小值
int min = prices[0];
for (int i = 1; i < prices.length; i++) {
// 更新最小值
min = Math.min(min, prices[i]);
// 當天賣出的最大利潤
int profit = prices[i] - min;
// 前i天買賣一次的最大利潤
dp[i] = Math.max(dp[i - 1], profit);
}
return dp[prices.length - 1];
}
}