題目描述1

Say you have an array for which the i th element is the price of a given stock on day i.
Design an algorithm to find the maximum profit. You may complete as many transactions as you like (ie, buy one and sell one share of the stock multiple times). However, you may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

解析：可以多次買賣，那么就簡單了，只需要在波谷買進，波峰賣出就可以了

public class Solution {public int maxProfit(int[] prices) {int maxProfile=0;for(int i=0;i<prices.length-1;i++){if(prices[i]<prices[i+1]){maxProfile+=prices[i+1]-prices[i];}}return maxProfile;} }

---

題目描述2

Say you have an array for which the i th 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.

解析：題目表示最多只能買賣一次

public class Solution {public int maxProfit(int[] prices) {int maxProfile=0;for(int i=0;i<prices.length;i++){for(int j=i+1;j<prices.length;j++){maxProfile=maxProfile>(prices[j]-prices[i])?maxProfile:(prices[j]-prices[i]);}}return maxProfile;} }

---

題目描述3（較為復雜些了）

Say you have an array for which the i th element is the price of a given stock on day i.
Design an algorithm to find the maximum profit. You may complete at most two transactions.
Note:
You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

解析：最多買賣兩次，可以以i為分界線，然后在i的左側(cè)搜索最大的利潤，在i的右側(cè)也搜索最大的利潤，最后算總的利潤。

測試用例
輸入：
[6,1,3,2,4,7]

輸出：
7

import java.util.*; public class Solution {public int maxProfit(int[] prices) {int maxProfile=0;int length=prices.length;for(int i=0;i<length;i++){int leftMax=0,rightMax=0;for(int j=0;j<i;j++){//搜索左側(cè)的最大利潤for(int k=j+1;k<=i;k++){int temp =prices[k]-prices[j];leftMax=leftMax>temp?leftMax:temp;}}for(int j=i+1;j<length;j++){//搜索右側(cè)的最大利潤for(int k=j+1;k<length;k++){int temp =prices[k]-prices[j];rightMax=rightMax>temp?rightMax:temp;}}if(leftMax+rightMax>maxProfile){maxProfile=leftMax+rightMax;}}return maxProfile;} }

總結(jié)

以上是生活随笔為你收集整理的《leetcode》best-time-to-buy-and-sell-stock-i-ii-iii的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。