算法设计与分析--求最大子段和问题
问题描述:
给定由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];
else
b[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 10000
int 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];
else
b[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();
else
num[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;
}
测试结果:
分享到:
相关推荐
算法设计与分析--求最大子段和问题(蛮力法、分治法、动态规划法) C++实现.rar
蛮力法、分治法和动态规划法设计最大子段和问题的算法,一、试分别利用蛮力法、分治法和动态规划法求解最大子段和问题,要求写出C/C++程序实现和算法的效率分析。程序运行结果要同时给出最大子段和的值以及由哪个子段...
最近对问题 最大子段和(分治法) 最长公共子序列问题 最大子段和(动态规划)
本算法是用C++实现最大子段和问题,包括蛮力法,分治法和动态规划法的实现及时间效率的对比
最大子段和/三种方法/c++语言/(内有报告) 蛮力法,动态规划法,分治法。 可比较时间,随机输入数据......
实验二 用动态规划法求解0/1背包问题 实验三 用贪心算法求解Prim算法 实验四 用回溯法求解N后问题 实验五 用分支限界法实现旅行售货员问题 这些实验的大部分源代码都是书上的, 我用的是WindowsXP SP2 VisualC++6.0...
主要是对 1 - 8章 以及 第10章中的课后习题进行代码解答,主要包括的章节有第1章概论、第2章递归算法设计技术、第3章分治法、第4章蛮力法、第5章回溯法、第6章分支限界法、第7章贪心法、第8章动态规划以及第10章计算...
第2章介绍常用数学工具,第3章从算法的观点介绍了NP完全理论,从第4章~第12章分别介绍了蛮力法、分治法、减治法、动态规划法、贪心法、回溯法、分支限界法、概率算法和近似算法等算法设计技术。课程中所配算法均给出...
一、数据结构知识点总结整理 3 2.数据结构的定义: 4 3.数据结构的知识: 9 ...1.7 动态规划法 115 1.8 回溯法 119 1.9 分支定界法: 120 2.几个重要的算法程序 121 2.1 堆排序 121 2.2 归并排序 122
包含:一、分治法求最近点对问题 二、采用贪心算法解决单会场安排问题 三、基于动态规划的游艇租用问题 四、回溯法解决部落卫队问题 五、分支定界解决N皇后问题
它深入浅出地介绍了大量的算法及相关的数据结构,以及用于解决一些复杂计算问题的高级策略(如动态规划、贪心算法、平摊分析等),重点在于算法的分析和设计。对于每一个专题,作者都试图提供目前最新的研究成果及样例...
第2章介绍常用数学工具,第3章从算法的观点介绍了NP完全理论,从第4章~第12章分别介绍了蛮力法、分治法、减治法、动态规划法、贪心法、回溯法、分支限界法、概率算法和近似算法等算法设计技术。课程中所配算法均给出...
里面有些是用JavaScript写的算法 有些是C++写的 分治法 动态规划 回溯法 贪心法
动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中,可能会有许多可行解...动态规划算法与分治法类似,其基本思想也是将待求解问题分解成若干个子问题,先求解子问题,然后从这些子问题的解得到原问题的解
三个cpp文件分别实现 动态规划最长公共子序列,分治法实现最近点对问题,最佳调度问题的回溯
包含大学算法分析设计全部课程的代码以及实验内容,精心进行编写,使用latex进行了编排,算法包括动态规划,贪心,分支等各种算法,包含0-1背包等多问题解决策略。
本书是数据结构和算法分析的经典教材,书中使用主流的程序设计语言C++作为具体的实现语言。书的内容包括表、栈、队列、树、散列表、优先队列、排序、不相交集算法、图论算法、算法分析、算法设计、摊还分析、查找...
专题十:算法分析与设计 1.常用的算法设计方法: 1.1 迭代法 1.2 穷举搜索法 1.3 递推法 1.4 递归法 1.5 贪婪法 1.6 分治法 1.7 动态规划法 1.8 回溯法 算法基础部分: 算法是对特定问题求解步骤的一...
用分治法,动态规划求最佳路径,解决的是金字塔钻石矿工的问题,是自己写的作业代码