首页 > 代码库 > [Leetcode] Best Time to Buy and Sell Stock III

[Leetcode] Best Time to Buy and Sell Stock III

2024-07-07 20:57:26   226人阅读

Question:

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

 

 1 public class Solution {
 2     public int maxProfit(int[] prices) {
 3         int n=prices.length;
 4         if (n <= 1)
 5             return 0;
 6         int[] l2r = new int[n];
 7         int[] r2l = new int[n];
 8         l2r[0] = 0;
 9         r2l[n-1] = 0;
10         int minn = prices[0];
11         for (int i = 1; i < n; i++) {
12             minn = Math.min(minn, prices[i]);
13             l2r[i] = Math.max(l2r[i - 1], prices[i] - minn);
14         }
15         int maxx = prices[n - 1];
16         for(int i=n-2;i>=0;i--){
17             maxx=Math.max(maxx, prices[i]);
18             r2l[i]=Math.max(r2l[i+1], maxx-prices[i]);
19         }
20         int result=l2r[n-1];
21         for(int i=0;i<n-1;i++){
22             result=Math.max(result, l2r[i]+r2l[i+1]);
23         }
24         return result;
25     }
26 }

 

Solution: dp.
max profit = max { l2r[0...i] + r2l[i+1...N-1] }.
0 <= i <= N-1
从左到右扫一遍，再从右到左扫一遍。

 


联系
我们