- // ConsoleApplication8.cpp : 定义控制台应用程序的入口点。
- //
- #include "stdafx.h"
- #include <stdio.h>
- #include <stdlib.h>
- #include <iostream>
- using namespace std;
- template <class T>
- int getArrayLen(T& array) //使用模板定义一个函数getArrayLen,该函数将返回数组array的长度
- {
- return (sizeof(array) / sizeof(array[0]));
- }
- int _tmain(int argc, _TCHAR* argv[])
- {
- void findMaxSubArray(int [],int);
- int a[]={5,-100,34535,32,10,5,4,-100,2}; //初始化数组
- int len=getArrayLen(a);
- findMaxSubArray(a,len);
- system("pause");
- return 0;
- }
- void findMaxSubArray(int a[],int len)
- {
- //声明
- int getSubArraysPreIterator(int [],int ,int,int );
- int getSubArrayMid(int ,int ,int ,int [],int );
- //低位下标
- int low=0;
- //高位下标
- int high=0;
- //中间位数
- int mid=0;
- //最大子数组
- int sum=0; //第一种情况下
- int sumAfter=0; //第二种情况下
- int sumMid=0; //第三种情况下
- int mid_RightPos=0; //横跨中间数组的右边界
- int mid_LeftPos=0; //横跨中间的数组的左边界
- int sumMidFromRight=0; //从右边开始计算
- int arrLen=len;//数组长度
- //如果数组中只有一个元素
- if(arrLen==1)
- {
- cout<<" 最大子数组是:"<<a[0]<<endl;
- }
- mid=arrLen/2; //算出中间的位置
- /*有3种可能的情况
- 1.最大子数组在中位数的左边
- 2.最大子数组在中位数的右边
- 3.最大子数组横跨中间*/
- //先求第一种情况
- for(int i=mid;i>=0;i--)
- {
- sum=sum+a[i];
- int sum_=getSubArraysPreIterator(a,mid,i,0);
- if(sum<sum_)
- {
- sum=getSubArraysPreIterator(a,mid,i,0);
- low=i; //最大子数组左边的边界。
- }
- }
- cout<<"最大子数组(左)是:"<<sum<<endl;
- cout<<"low:"<<low<<endl;
- //第二种情况
- for(int i=mid+1;i<arrLen;i++)
- {
- sumAfter=sumAfter+a[i];
- int sum_After=getSubArraysPreIterator(a,mid,i,1);
- if(sumAfter<sum_After)
- {
- sumAfter=getSubArraysPreIterator(a,mid,i,1);
- high=i;
- }
- //如果没进入上面的IF语句,则表示是最后一个
- if(high==0&&i==arrLen-1)
- {
- high=i;
- }
- }
- cout<<"最大子数组(右)是:"<<sumAfter<<endl;
- cout<<"high:"<<high<<endl;
- //确定了最低位的下标和最高位的下标,下面进行跨中位运算
- for(int i=low+1;i<high;i++)
- {
- sumMid=sumMid+a[i];
- //从LOW开始考虑问题
- int sumMid_=getSubArrayMid(low,high,i,a,0);
- if(sumMid<sumMid_)
- {
- sumMid=getSubArrayMid(low,high,i,a,0);
- mid_RightPos=i;
- }
- //从HIGH开始考虑问题
- int sumMid_High=getSubArrayMid(low,high,i,a,1);
- if(sumMid<sumMid_High)
- {
- sumMidFromRight=getSubArrayMid(low,high,i,a,1);
- mid_LeftPos=i;
- }
- //比较大小
- if(sumMid<sumMidFromRight)
- {
- sumMid=sumMidFromRight;
- mid_RightPos=mid_LeftPos;
- }
- }
- cout<<"横跨中间的子数组是:"<<sumMid<<endl;
- cout<<"横跨中间的数组的右边界是:"+mid_RightPos<<endl;
- //比较三个求出来的值的大小,确定谁才是最大子数组。
- if(sum>sumAfter)
- {
- if(sum>sumMid)
- {
- cout<<"最终结果:"<<sum<<"为最大子数组"<<endl;
- }
- else
- {
- cout<<"最终结果:"<<sumMid<<"为最大子数组"<<endl;
- }
- }
- else
- {
- if(sum<sumMid)
- {
- if(sumMid>sumAfter)
- {
- cout<<"最终结果:"<<sumMid<<"为最大子数组"<<endl;
- }
- else
- {
- cout<<"最终结果:"<<sumAfter<<"为最大子数组"<<endl;
- }
- }
- }
- }
- //根据下标获得子数组(前一次迭代的和的结果)
- int getSubArraysPreIterator(int a[],int mid,int i,int flag)
- {
- //获得要求的子数组的跨度
- int span=mid-i;
- //总和
- int sum=0;
- //左边
- if(flag==0)
- {
- //计算前一次元素的和,以和上面的后一次的函数所得到的和做笔记
- for(int k=mid;k>=i+1;k--)
- {
- sum+=a[k];
- }
- return sum;
- }
- //右边
- if(flag ==1)
- {
- for(int k=mid+1;k<i;k++)
- {
- sum+=a[k];
- }
- return sum;
- }
- }
- //获得子数组(跨中线)
- //注意:因为从中线可能是从中线的左边,或者是右边的数组是最大子数组,所以要区别对待
- int getSubArrayMid(int low,int high,int i,int a[],int flag)
- {
- int sum=0;
- if(flag==0)
- {
- for(int k=low+1;k<i;k++)
- {
- sum+=a[k];
- }
- return sum;
- }
- else if(flag==1)
- {
- for(int k=high-1;k>i;k--)
- {
- sum+=a[k];
- }
- return sum;
- }
- }
- //该片段来自于http://www.codesnippet.cn/detail/2303201511962.html
来源: http://www.codesnippet.cn/detail/2303201511962.html