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那里面的讨论区，你可以逛逛哦。题主，你懂的。