最大子数组问题:找出数组中和最大的最大的非空连续子数组.
这里定义一个ret的类来进行存储三个值.用public只是用来方便读取和使用..
#include "stdafx.h"
#include<iostream>
using namespace std;
class ret
{
public:
ret(void){};
ret(int x,int y ,int z):max_left(x),max_right(y),right_sum(0){}
int max_left;
int max_right;
int right_sum;
};
ret FindMaxCrossingSubarray(int *arr,int low,int mid,int high);
ret findMaxSub(int *arr,int low,int high);
int _tmain(int argc, _TCHAR* argv[])
{
int arr[]={-1,-2,2,8,2,1,-2,4};
ret test= findMaxSub(arr,1,sizeof(arr)/sizeof(arr[0]));
cout<<"从第"<<test.max_left<<"个数到第"<<test.max_right<<"的和最大,和为:"<<test.right_sum<<endl;
return 0;
}
ret findMaxSub(int *arr,int low,int high)
{
if(low==high){
ret temp1;
temp1.max_left=low;
temp1.max_right=high;
temp1.right_sum=arr[low-1];
return temp1;
}
else
{
int mid = (low +high)/2;
ret temp2 = findMaxSub(arr,low,mid);
ret temp3 = findMaxSub(arr,mid+1,high);
ret temp4 = FindMaxCrossingSubarray(arr,low,mid,high);
if(temp2.right_sum>=temp3.right_sum&&temp2.right_sum>=temp4.right_sum)
return temp2;
else if(temp3.right_sum>=temp2.right_sum&&temp3.right_sum>=temp4.right_sum)
return temp3;
else return temp4;
}
}
ret FindMaxCrossingSubarray(int *arr,int low,int mid,int high)
{
ret temp;
int left_sum =-99999,sum = 0,max_left=0;
for (int i =mid-1;i>=low-1;--i)
{
sum=sum+arr[i];
if(sum>left_sum)
{
left_sum = sum;
max_left = i;
}
}
int right_sum =-99999,rsum = 0,max_right=0;
for (int j =mid;j<=high-1;++j)
{
rsum=rsum+arr[j];
if(rsum>right_sum)
{
right_sum = rsum;
max_right = j;
}
}
temp.max_left=max_left+1;
temp.max_right=max_right+1;
temp.right_sum=left_sum+right_sum;
return temp;
}
#include "stdafx.h"
#include<iostream>
using namespace std;
class ret
{
public:
ret(void){};
ret(int x,int y ,int z):max_left(x),max_right(y),right_sum(0){}
int max_left;
int max_right;
int right_sum;
};
ret FindMaxCrossingSubarray(int *arr,int low,int mid,int high);
ret findMaxSub(int *arr,int low,int high);
int _tmain(int argc, _TCHAR* argv[])
{
int arr[]={-1,-2,2,8,2,1,-2,4};
ret test= findMaxSub(arr,1,sizeof(arr)/sizeof(arr[0]));
cout<<"从第"<<test.max_left<<"个数到第"<<test.max_right<<"的和最大,和为:"<<test.right_sum<<endl;
return 0;
}
ret findMaxSub(int *arr,int low,int high)
{
if(low==high){
ret temp1;
temp1.max_left=low;
temp1.max_right=high;
temp1.right_sum=arr[low-1];
return temp1;
}
else
{
int mid = (low +high)/2;
ret temp2 = findMaxSub(arr,low,mid);
ret temp3 = findMaxSub(arr,mid+1,high);
ret temp4 = FindMaxCrossingSubarray(arr,low,mid,high);
if(temp2.right_sum>=temp3.right_sum&&temp2.right_sum>=temp4.right_sum)
return temp2;
else if(temp3.right_sum>=temp2.right_sum&&temp3.right_sum>=temp4.right_sum)
return temp3;
else return temp4;
}
}
ret FindMaxCrossingSubarray(int *arr,int low,int mid,int high)
{
ret temp;
int left_sum =-99999,sum = 0,max_left=0;
for (int i =mid-1;i>=low-1;--i)
{
sum=sum+arr[i];
if(sum>left_sum)
{
left_sum = sum;
max_left = i;
}
}
int right_sum =-99999,rsum = 0,max_right=0;
for (int j =mid;j<=high-1;++j)
{
rsum=rsum+arr[j];
if(rsum>right_sum)
{
right_sum = rsum;
max_right = j;
}
}
temp.max_left=max_left+1;
temp.max_right=max_right+1;
temp.right_sum=left_sum+right_sum;
return temp;
}