The test data is really weak


  • 0
    B

    I use the code of the first problem in this problem series. It's quite straight forward to extend to this two-buy-in-buy-out case.

    class Solution {
    public:
        int maxProfitPart(vector<int>& prices, int a, int b) {
    		if(prices.size() < 2)return 0;
    		int mins = prices[a], maxP = 0;
    		for (int i = a + 1; i < b; ++i) {
    			if(prices[i - 1] < mins) {
    				mins = prices[i - 1];
    			}
    			if(maxP< prices[i] - mins)
    				maxP= prices[i] - mins;
    		}
    		return maxP;
        }
        int maxProfit(vector<int>& prices) {
    		if(prices.size() < 2)return 0;
    		int res = 0, maxP = 0, profit;
    		for (int i = 1, L = prices.size(); i < L; ++i) {
    			if(prices[i] - prices[i - 1] > 0) {
    				profit = maxProfitPart(prices, 0, i + 1) + maxProfitPart(prices, i + 1, L);
    				if(profit > maxP) maxP = profit;
    			}
    		}
    		profit = maxProfitPart(prices, 0, prices.size());
    		if(profit > maxP) maxP = profit;
    		return maxP;
        }
    };
    

    I have no change to find the O(n) algorithm because this O(n^2) algorithm is fast enough for the test data, which is about 19ms. But this is not why I say the test data is weak.

    It's weak because I make a typo at first, instead of

    if(prices[i] - prices[i - 1] > 0)
    

    I typed

    if(prices[i] - prices[0] > 0)
    

    but it passed 181 cases out of 198!


Log in to reply
 

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