LeetCode: Best Time to Buy and Sell Stock III

思路对的，但是没弄好code，改了挺多，最后还是runtime exceed了，看了网上答案再把自己的code改了改

 1 class Solution {
 2 public:
 3     int maxProfit(vector<int> &prices) {
 4         // Start typing your C/C++ solution below
 5         // DO NOT write int main() function
 6         if (prices.size() <= 1) return 0;
 7         int size = prices.size();
 8         vector<int> left(size);
 9         vector<int> right(size);
10         int minprice = prices[0];
11         left[0] = 0;
12         for (int i = 1; i < size; i++) {
13             minprice = min(minprice, prices[i]);
14             left[i] = max(left[i-1], prices[i]-minprice);
15         }
16         int maxprice = prices[size-1];
17         right[size-1] = 0;
18         for (int i = size-2; i >= 0; i--) {
19             maxprice = max(maxprice, prices[i]);
20             right[i] = max(right[i+1], maxprice - prices[i]);
21         }
22         int maxprofit = 0;
23         for (int i = 0; i < size; i++) {
24              maxprofit = max(maxprofit, left[i]+right[i]);
25         }
26         return maxprofit;
27     }
28 };

C#:

 1 public class Solution {
 2     public int MaxProfit(int[] prices) {
 3         int size = prices.Count();
 4         if (size < 1) return 0;
 5         int[] leftProfit = new int[size];
 6         int[] rightProfit = new int[size];
 7         int leftMinPrice = prices[0];
 8         int rightMaxPrice = prices[size-1];
 9         leftProfit[0] = 0;
10         rightProfit[size-1] = 0;
11         for (int i = 1; i < prices.Count(); i++) {
12             leftProfit[i] = Math.Max(leftProfit[i-1], prices[i] - leftMinPrice);
13             leftMinPrice = Math.Min(leftMinPrice, prices[i]);
14         }
15         for (int i = size-2; i >= 0; i--) {
16             rightProfit[i] = Math.Max(rightProfit[i+1], rightMaxPrice - prices[i]);
17             rightMaxPrice = Math.Max(rightMaxPrice, prices[i]);
18         }
19         int maxProfit = 0;
20         for (int i = 0; i < size; i++) maxProfit = Math.Max(maxProfit, leftProfit[i] + rightProfit[i]);
21         return maxProfit;
22     }
23 }

View Code

java

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