c++ - leetcode 121. Best Time to Buy and Sell Stock
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;
}
};
