Failed in the last test, is there anyone can help?


  • 0
    P
     class Solution {
     public:
    	 int maxProfit(vector<int>& prices) {
    		 vector<int> diff;
    		 if (prices.size() == 0)return 0;
    		 int *sum = new int [prices.size()];
    		 int buy1 = 0, sell1 = 0;
    		 int buy2 = 0, sell2 = 0;
    		 int i = 1, j = 0;
    		 sum[0] = 0;
    		 diff.push_back(0);
    		 int d;
    		 for (i = 1; i < prices.size(); i++)
    		 {
    			 d = prices[i] - prices[i - 1];
    			 if (diff[j] * d >= 0)
    			 {
    				 diff[j] += d;
    			 }
    			 else
    			 {
    				 diff.push_back(d);
    				 j++;
    			 }
    		 }
    		 for (i = 0; i < diff.size(); i++)
    		 {
    			 if (diff[i]>0)
    			 {
    				 if (buy1 == 0)
    				 {
    					 buy1 = diff[i];
    					 sell1 = 0;
    				 }
    				 else
    				 {
    					 if (buy2 == 0)
    					 {
    						 buy2 = diff[i];
    						 sell2 = 0;
    					 }
    					 else
    					 {
    						 int k1 = diff[i] + buy1 - sell1 + buy2 + sell2; //merge buy1 and buy2
    						 int k2 = buy1 + buy2 - sell2 + diff[i]; //merge buy2 and today
    						 int k3 = diff[i] + buy1; //abandon buy2
    						 int k4 = diff[i] + buy2; //abandon buy1
    						 int k5 = sum[i - 1]; //abandon today
    						 int maxchoice = max(max(max(max(k1, k2), k3), k4), k5);
    						 if (maxchoice == k5)
    						 {
    							 sell1 = sell1 - diff[i];
    							 sell2 = sell2 - diff[i];
    						 }
    						 else
    						 if (maxchoice == k1)
    						 {
    							 buy1 = buy1 - sell1 + buy2 + sell2;
    							 sell1 = sell2;
    							 buy2 = diff[i];
    							 sell2 = 0;
    						 }
    						 else
    						 if (maxchoice == k2)
    						 {
    							 buy2 = buy2 - sell2 + diff[i];
    							 sell2 = 0;
    						 }
    						 else
    						 if (maxchoice == k4)
    						 {
    							 buy1 = buy2;
    							 sell1 = sell2;
    							 buy2 = diff[i];
    							 sell2 = 0;
    						 }
    						 else
    						 if (maxchoice == k3)
    						 {
    							 buy2 = diff[i];
    							 sell2 = 0;
    						 }
    					 }
    				 }
    			 }
    			 else
    			 {
    				 sell1 -= diff[i];
    				 sell2 -= diff[i];
    				 sum[i] = sum[i - 1];
    			 }
    			 sum[i] = buy1 + buy2;
    		 }
    		 return sum[diff.size()-1];
    	 }
     };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.