C++ recursive, TLE...


  • 0
    class Solution {
    public:
        int oneBuy(vector<int>& prices, int l, int r) {
            if(l==r) return 0;
            int res = 0;
            int minPrice[r-l+1];
            minPrice[0] = prices[l];
            for(int i=l+1;i<=r;i++) {
                minPrice[i-l] = min(minPrice[i-l-1],prices[i]);
                res = max(res,prices[i]-minPrice[i-l]);
            }
            return res;
        }
        int work(vector<int>& prices, int l, int r) {
            int len = r-l+1;
            int ans = oneBuy(prices,l,r);
            if(len<5) return ans;
            for(int i=l+2;i<=r-2;i++) {
                ans = max(ans,work(prices,l,i-1)+work(prices,i+1,r));
            }
            return ans;
        }
        int maxProfit(vector<int>& prices) {
            if(prices.size()<2) return 0;
            return work(prices,0,prices.size()-1);
        }
    };
    

Log in to reply
 

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