My ugly C++ solution 12ms


  • 0
    class Solution {
    public:
        int maxProfit(vector<int>& prices) {
            int len = prices.size();
            if(len<2) return 0;
            vector<int> newPrices;
            newPrices.push_back(prices[0]);
            int index = 1;
            while(index<len-1){
                if(prices[index]==newPrices[newPrices.size()-1]){
                    index++;
                }else if(prices[index]>newPrices[newPrices.size()-1] && prices[index+1]>prices[index]){
                    index++;
                }else if(prices[index]<newPrices[newPrices.size()-1] && prices[index+1]<prices[index]){
                    index++;
                }else{
                    newPrices.push_back(prices[index]);
                    index++;
                }
            }
            newPrices.push_back(prices[len-1]);
            int newLen = newPrices.size();
            int profit=0;
            int tmp;
            for(int i=0; i<newLen; i++){
                for(int j=i+1; j<newLen; j++){
                    tmp = newPrices[j]-newPrices[i];
                    if(tmp>profit) profit=tmp;
                }
            }
            return profit;
        }
    };
    

Log in to reply
 

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