c++ - leetcode 121. Best Time to Buy and Sell Stock

Question

https://leetcode.com/problems...

我是看了算法导论里面，将这个问题转化成求一个数组最小子数组和的问题，下面是我的代码。我在xcode里面跑是对的，然后在leetcode上面，相同的输入，死活出现错误结果。

Your input

[7,1,5,3,6,4]
Your answer

33
Expected answer

5

这组输入，我在ide里面是对的，在leetcode的测试里面是错的，求解

class Solution {
public:
    int maxProfit(vector<int>& prices) {
    //将prices数组转化为代表每日价格变化的数组
    //为了能保证in-place，需要从后面向前面转换
        if (prices.empty())
            return 0;
        for(int i=prices.size()-1;i>0;i--){
            prices[i]=prices[i-1]-prices[i];
            prices[i]*=-1;
        }
        prices[0]=0;
        return findMaxSumSubarray(prices,0,prices.size());
    }
private:
    //返回跨越中点的最大子数组之和
    int findMaxSumCrossSubarray(vector<int> prices, int low,int high){
        int mid=(low+high)/2;
        int rightMaxSum=0;
        int tempSum=0;
        for(int i=mid+1;i<high;i++){
            tempSum+=prices[i];
            rightMaxSum=max(rightMaxSum,tempSum);
        }
        int leftMaxSum=0;
        tempSum=0;
        for(int i=mid-1;i>=low;i--){
            tempSum+=prices[i];
            leftMaxSum=max(leftMaxSum,tempSum);
        }
        return (leftMaxSum+rightMaxSum+prices[mid]);
    }
    //返回prices数组中的最大子数组之和
    int findMaxSumSubarray(vector<int> prices, int low,int high){
        if(low==high)
            return prices[low];
        int mid=(low+high)/2;
        int leftSum=findMaxSumSubarray(prices,low,mid);
        int rightSum=findMaxSumSubarray(prices,mid+1,high);
        int midSum=findMaxSumCrossSubarray(prices,low,high);
        if(leftSum>=rightSum&&leftSum>=midSum)
            return leftSum;
        else if(rightSum>=leftSum&&rightSum>=midSum)
            return rightSum;
        else return midSum;
    }
};

Answer 1

題主下次記得把主函數什麼的也都貼上來…

注意到樓上的截圖，對於同一個輸入會有不同的輸出，所以猜測是訪問溢出

又看到到遞歸的時候，分別使用了low,mid和mid+1,high作為參數傳遞，所以知道對於findMaxSumSubarray(prices,low,high)，其考察的是[low,high]範圍內的數據

然而題主又在一開始的地方寫了findMaxSumSubarray(prices,0,prices.size());

是不是應該改成findMaxSumSubarray(prices,0,prices.size()-1);呢~

Answer 2

你這做的也太複雜了吧。 。我的題解 https://github.com/hanzichi/l...

Answer 3

我多編譯運行幾次，發現答案不一致。應該是題主你的演算法有問題，題主再思考一下。這題目程式碼寫不到這麼複雜，題主可以再思考一下。我就不給你檢查代碼了。 。 。太長了，這些演算法題，多刷刷，做完一道再去看看別人的程式碼，學習別人的程式碼，可能更有收穫。 leetcode那裡面的討論區，你可以逛逛哦。題主，你懂的。