Best Time to Buy and Sell Stock III

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).

C++:
01 class Solution {
02 public:
03     int maxProfit(vector<int> &prices) {
04         // Start typing your C/C++ solution below
05         // DO NOT write int main() function
06         int n=prices.size();
07         if(n<=1)
08             return 0;
09         vector<int> profit1(n);
10         vector<int> profit2(n);
11         int min=prices[0];
12         int max=prices[n1];
13         int prof1=0;
14         int prof2=0;
15         for(int i=0;i<n;i++)
16         {
17             if(prices[i]<min)
18             {
19                 min=prices[i];
20             }
21             if(prices[i]min>prof1)
22             {
23                 prof1=prices[i]min;
24             }
25             profit1[i]=prof1;
26         }
27         for(int i=n1;i>=0;i)
28         {
29             if(prices[i]>max)
30             {
31                 max=prices[i];
32             }
33             if(maxprices[i]>prof2)
34             {
35                 prof2=maxprices[i];
36             }
37             profit2[i]=prof2;
38         }
39         int result=profit1[n1];
40         for(int i=0;i<n1;i++)
41         {
42             if(profit1[i]+profit2[i+1]>result)
43                 result=profit1[i]+profit2[i+1];
44         }
45         return result;
46     }
47 };
Advertisements
This entry was posted in Array and linked list. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s