在这个系列，我打算把我在leetcode上发布的题解也在博客上发布一遍。
位置：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock/
写到这一题的时候正好看到《算法导论》P38 4.1最大子数组问题。我按照《算法导论》中的伪代码写了题解，虽然这个方法对于这道题有点过于复杂，但对于练习这个分治思想倒是很不错，具体的算法解释可以看《算法导论》。
class Solution {
public:
int findCrossMax(vector<int>& a,int left,int mid,int right){
int leftMax=-1000000;
int sum=0;
for(int i=mid;i>=left;i--){
sum=sum+a[i];
if(sum>leftMax)
leftMax=sum;
}
int rightMax=-1000000;
sum=0;
for(int i=mid+1;i<=right;i++){
sum=sum+a[i];
if(sum>rightMax)
rightMax=sum;
}
return rightMax+leftMax;
}
int findMax(vector<int>& a,int left,int right){
if(left==right)
return a[left];
else{
int mid=(left+right)/2;
int leftsum=findMax(a,left,mid);
int rightsum=findMax(a,mid+1,right);
int crosssum=findCrossMax(a,left,mid,right);
if(leftsum>=rightsum&&leftsum>=crosssum)
return leftsum;
else if(rightsum>=leftsum&&rightsum>=crosssum)
return rightsum;
else
return crosssum;
}
}
int maxProfit(vector<int>& prices) {
int n=prices.size();
if(n==1)
return 0;
vector<int> array;
for(int i=0;i<n-1;i++)
array.push_back(prices[i+1]-prices[i]);
int ans=findMax(array,0,n-2);
return max(0,ans);
}
};
这个方法的递推式为：T(n)=2T(n/2)+O(n)。
在《算法导论》P42的练习4.1-5提供了另一种思路，用C++语言实现如下：
class Solution {
public:
int findMax(vector<int>& a,int low,int high){
if(low==high)
return a[low];
else{
int preMax=findMax(a,low,high-1);
int sum=0;
int nMax=-1000000;
for(int i=high;i>=low;i--){
sum=sum+a[i];
if(sum>nMax)
nMax=sum;
}
return max(nMax,preMax);
}
}
int maxProfit(vector<int>& prices) {
int n=prices.size();
if(n==1)
return 0;
vector<int> array;
for(int i=0;i<n-1;i++)
array.push_back(prices[i+1]-prices[i]);
int ans=findMax(array,0,n-2);
return max(0,ans);
}
};
这个方法的递推式为T(n)=T(n-1)+O(n)。
通过递推式的对比不难得出为什么方法一没有超时，而练习中的这个方法超时了。