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

Next time the questioner remembers to post the main function and so on...

I noticed in the screenshot above that there are different outputs for the same input, so I guess it is an access overflow

When we see the recursion, we use low,mid and mid+1,high as parameters respectively, so we know that for findMaxSumSubarray(prices,low,high), it examines the data within the range of [low,high]

However, the questioner wrote findMaxSumSubarray(prices,0,prices.size());

at the beginning Should

be changed to findMaxSumSubarray(prices,0,prices.size()-1);~

Answer 2

What you are doing is too complicated. . My solution https://github.com/hanzichi/l...

Answer 3

I compiled and ran it several times and found that the answers were inconsistent. There should be a problem with your algorithm. Please think about it again. The code for this question is not that complicated to write, so the question owner can think about it again. I won't check the code for you. . . It's too long. It may be more rewarding to brush up on these algorithm questions more, and then look at other people's codes after completing one, and learn from other people's codes. You can browse the discussion area in leetcode. Title, you know.