アルゴリズムの導論の第4章:最も大きいサブ配列-再帰、暴力と線形アルゴリズム
4555 ワード
#include <iostream>
#include <vector>
#include <tuple>
#include <climits>
using namespace std;
tuple<int,int,int> maxCrossSubarray(vector<int> &vec,int low,int mid,int high)
{
int leftSum=INT_MIN;
int sum=0;
int leftBoard=mid;
for(int i=mid;i>=low;--i){
sum+=vec[i];
if(sum>leftSum){
leftSum=sum;
leftBoard=i;
}
}
int rightSum=INT_MIN;
int sum2=0;
int rightBoard=mid+1;
for(int j=mid+1;j<=high;j++){
sum2+=vec[j];
if(sum2>rightSum){
rightSum=sum2;
rightBoard=j;
}
}
return (make_tuple(leftBoard,rightBoard,leftSum+rightSum));
}
tuple<int,int,int> maxSubarray(vector<int> &vec,int low,int high)
{
if(high==low)
return(make_tuple(low,high,vec[high]));
else{
size_t mid=(low+high)/2;
tuple<int,int,int> leftTuple;
tuple<int,int,int> rightTuple;
tuple<int,int,int> corssTuple;
leftTuple=maxSubarray(vec,low,mid);
rightTuple=maxSubarray(vec,mid+1,high);
corssTuple=maxCrossSubarray(vec,low,mid,high);
if(get<2>(leftTuple)>get<2>(rightTuple)&&get<2>(leftTuple)>get<2>(corssTuple))
return leftTuple;
else if(get<2>(rightTuple)>get<2>(leftTuple)&&get<2>(rightTuple)>get<2>(corssTuple))
return rightTuple;
else
return corssTuple;
}
}
tuple<int,int,int> naiveMaxSub(const vector<int> &vec)
{
int maxSum=INT_MIN;
int thisSum=0;
int leftBoard=0,rightBoard=0;
int i,j;
for(i=0;i<vec.size()-1;i++)
{
thisSum=vec[i];
if(thisSum>maxSum)
{
maxSum=thisSum;
leftBoard=i;
rightBoard=i;
}
for(j=i+1;j<vec.size();j++)
{
thisSum+=vec[j];
if(thisSum>maxSum)
{
maxSum=thisSum;
leftBoard=i;
rightBoard=j;
}
}
}
return(make_tuple(leftBoard,rightBoard,maxSum));
}
tuple<int,int,int> linerMaxSub(vector<int> &vec)
{
int maxSum=INT_MIN;//
int thisSum=0;
int leftBoard=0,rightBoard=0;
int tmpleftBoard=0,tmprightBoard=0;
for(int i=0;i<vec.size();++i)
{
thisSum+=vec[i];
if(thisSum>maxSum)
{
maxSum=thisSum;
leftBoard=tmpleftBoard;
rightBoard=tmprightBoard=i;
}
if(thisSum<0)
{
thisSum=0;
tmpleftBoard=tmprightBoard=i+1;
}
}
return(make_tuple(leftBoard,rightBoard,maxSum));
}
int main()
{
int SIZE=100000;
int i=0;
vector<int> vec;
while(i<SIZE)
{
vec.push_back(rand()%1000-500);
i++;
}
cout<<vec.size()<<endl;
// , nlgn
clock_t start_time=clock();
tuple<int,int,int> t=maxSubarray(vec,0,vec.size()-1);
clock_t end_time=clock();
cout<<"Running time is: "<<
static_cast<double>(end_time-start_time)/CLOCKS_PER_SEC<<" S"<<endl;
cout<<get<0>(t)<<"__"<<get<1>(t)<<" sum: "<<get<2>(t)<<endl;
// , n^2
clock_t start_time2=clock();
tuple<int,int,int> t2=naiveMaxSub(vec);
clock_t end_time2=clock();
cout<<"Running time is: "<<
static_cast<double>(end_time2-start_time2)/CLOCKS_PER_SEC<<" S"<<endl;
cout<<get<0>(t2)<<"__"<<get<1>(t2)<<" sum: "<<get<2>(t2)<<endl;
//
clock_t start_time3=clock();
tuple<int,int,int> t3=linerMaxSub(vec);
clock_t end_time3=clock();
cout<<"Running time is: "<<
static_cast<double>(end_time3-start_time3)/CLOCKS_PER_SEC<<" S"<<endl;
cout<<get<0>(t3)<<"__"<<get<1>(t3)<<" sum: "<<get<2>(t3)<<endl;
}