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;
}
};我多编译运行几次，发现答案不一致。应该是题主你的算法存在问题，题主再思考一下吧。这道题目代码写不到这么复杂，题主可以再思考一下。我就不给你检查代码了。。。太长了，这些算法题，多刷刷，做完一道再去看看别人的代码，学习一下别人的代码，可能更有收获。leetcode那里面的讨论区，你可以逛逛哦。题主，你懂的。
题主下次记得把主函数什么的也都贴上来……
注意到楼上的截图，对于同一个输入会有不同的输出，所以猜测是访问溢出
又看到到递归的时候，分别使用了low,mid和mid+1,high作为参数传递，所以知道对于findMaxSumSubarray(prices,low,high)，其考察的是[low,high]范围内的数据
然而题主又在一开始的地方写了findMaxSumSubarray(prices,0,prices.size());
是不是应该改成findMaxSumSubarray(prices,0,prices.size()-1);呢~
你这做的也太复杂了吧。。我的题解 https://github.com/hanzichi/l...