我想在阿里巴巴网站开店_怎么做/北京seo全网营销

算法设计与分析--求最大子段和问题

问题描述：

给定由n个整数组成的序列(a1,a2, …,an)，求该序列形如

 的子段和的最大值，当所有整数均为负整数时，其最大子段和为0。

利用蛮力法求解：

int maxSum(int a[],int n)
{int maxSum = 0;int sum = 0;for(int i = 0; i < n; i++) //从第一个数开始算起{for(int j = i + 1; j < n; j++)//从i的第二个数开始算起{sum = a[i];a[i]  += a[j];if(a[i] > sum){sum = a[i];		//每一趟的最大值}}if(sum > maxSum){maxSum = sum;}}return maxSum;
}

利用分治法求解：

int maxSum(int a[],int left, int right)
{int sum = 0;if(left == right)	//如果序列长度为1，直接求解{if(a[left] > 0) sum = a[left];else sum = 0;}else {int center = (left + right) / 2;	//划分int leftsum = maxSum(a,left,center);	//对应情况1，递归求解int rightsum = maxSum(a, center + 1, right);//对应情况2， 递归求解int s1 = 0;int lefts = 0;for(int i = center; i >= left; i--)	//求解s1{lefts += a[i];if(lefts > s1) s1 = lefts;	//左边最大值放在s1}int s2 = 0; int rights = 0;for(int j = center + 1; j <= right; j++)//求解s2{rights += a[j];if(rights > s2) s2 =rights;}sum = s1 + s2;				//计算第3钟情况的最大子段和if(sum < leftsum) sum = leftsum;	//合并，在sum、leftsum、rightsum中取最大值if(sum < rightsum) sum = rightsum;}return sum;
}

利用动态规划法求解：

int DY_Sum(int a[],int n)
{int sum = 0;int *b = (int *) malloc(n * sizeof(int));	//动态为数组分配空间b[0] = a[0];for(int i = 1; i < n; i++){if(b[i-1] > 0)b[i] = b[i - 1] + a[i];elseb[i] = a[i];}for(int j = 0; j < n; j++){if(b[j] > sum)sum = b[j];}delete []b;		//释放内存return sum;
}

完整测试程序：

#include<iostream>
#include<time.h>
#include<Windows.h>
using namespace std;
#define MAX 10000int BF_Sum(int a[],int n)   
{int max=0;     int sum=0;        int i,j;for (i=0;i<n-1;i++)        {         sum=a[i];          for(j=i+1;j<n;j++)            {       if(sum>=max)                {                                         max=sum;                }  sum+=a[j];         }    }    return max;
}    
int maxSum1(int a[],int left, int right)
{int sum = 0;if(left == right)	//如果序列长度为1，直接求解{if(a[left] > 0) sum = a[left];else sum = 0;}else {int center = (left + right) / 2;	//划分int leftsum = maxSum1(a,left,center);	//对应情况1，递归求解int rightsum = maxSum1(a, center + 1, right);//对应情况2， 递归求解int s1 = 0;int lefts = 0;for(int i = center; i >= left; i--)	//求解s1{lefts += a[i];if(lefts > s1) s1 = lefts;	//左边最大值放在s1}int s2 = 0; int rights = 0;for(int j = center + 1; j <= right; j++)//求解s2{rights += a[j];if(rights > s2) s2 =rights;}sum = s1 + s2;				//计算第3钟情况的最大子段和if(sum < leftsum) sum = leftsum;	//合并，在sum、leftsum、rightsum中取最大值if(sum < rightsum) sum = rightsum;}return sum;
}int DY_Sum(int a[],int n)
{int sum = 0;int *b = (int *) malloc(n * sizeof(int));	//动态为数组分配空间b[0] = a[0];for(int i = 1; i < n; i++){if(b[i-1] > 0)b[i] = b[i - 1] + a[i];elseb[i] = a[i];}for(int j = 0; j < n; j++){if(b[j] > sum)sum = b[j];}delete []b;		//释放内存return sum;
}int main()
{int num[MAX];int i;const int n = 40;LARGE_INTEGER begin,end,frequency;QueryPerformanceFrequency(&frequency);//生成随机序列cout<<"生成随机序列：";srand(time(0));for(int i = 0; i < n; i++){if(rand() % 2 == 0)num[i] = rand();elsenum[i] = (-1) * rand();if(n < 100)cout<<num[i]<<" ";}cout<<endl;//蛮力法//cout<<"\n蛮力法:"<<endl;cout<"最大字段和：";QueryPerformanceCounter(&begin);cout<<BF_Sum(num,n)<<endl;QueryPerformanceCounter(&end);cout<<"时间:"<<(double)(end.QuadPart - begin.QuadPart) / frequency.QuadPart<<"s"<<endl;cout<<"\n分治法:"<<endl;cout<"最大字段和：";QueryPerformanceCounter(&begin);cout<<maxSum1(num,0,n)<<endl;QueryPerformanceCounter(&end);cout<<"时间:"<<(double)(end.QuadPart - begin.QuadPart) / frequency.QuadPart<<"s"<<endl;cout<<"\n动态规划法:"<<endl;cout<"最大字段和：";QueryPerformanceCounter(&begin);cout<<DY_Sum(num,n)<<endl;QueryPerformanceCounter(&end);cout<<"时间:"<<(double)(end.QuadPart - begin.QuadPart) / frequency.QuadPart<<"s"<<endl;system("pause");return 0;
}