最大子段和算法
最大子段和n 3算法
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14. int MaxSubseqSum1( int A[], int N ) { int ThisSum, MaxSum = 0; int i, j, k; for( i = 0; i MaxSum ) /* 如果刚得到的这个子列和更大 */ MaxSum = ThisSum; /* 则更新结果 */ } /* j循环结束 */ } /* i循环结束 */ return MaxSum; }
最大子段和n 2算法
int MaxSubseqSum2( int A[], int N )
{ int ThisSum, MaxSum = 0;
int i, j;
for( i = 0; i
ThisSum = 0; /* ThisSum是从A[i]到A[j]的子列和 */
for( j = i; j
ThisSum += A[j]; /*对于相同的i ,不同的j ,只要在j-1次循环的基础上累加1项即可*/ if( ThisSum > MaxSum ) /* 如果刚得到的这个子列和更大 */
MaxSum = ThisSum; /* 则更新结果 */
} /* j循环结束 */
} /* i循环结束 */
return MaxSum;
}
最大子段和nlongn 算法(分治)
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 s2) s2 =rights; } sum = s1 + s2; //计算第3钟情况的最大子段和 if(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
{
if(b[i-1] > 0)
b[i] = b[i - 1] + a[i];
else
b[i] = a[i];
}
for(int j = 0; j
{
if(b[j] > sum)
sum = b[j];
}
delete []b; //释放内存
return sum;
}
#include
#include
#include
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
{
sum=a[i];
for(j=i+1;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
{
rights += a[j];
if(rights > s2) s2 =rights;
}
sum = s1 + s2; //计算第3钟情况的最大子段和
if(sum
}
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
{
if(b[i-1] > 0)
b[i] = b[i - 1] + a[i];
else
b[i] = a[i];
}
for(int j = 0; 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
相关文章
- 基于蚁群算法求解最大团问题
- 基于微博网络的影响力最大化算法
- 数据挖掘十大经典算法
- 基于改进人工蜂群算法的K均值聚类算法
- 贪心算法思想
- 基于遗传算法的阈值图像分割研究
- 20**年计算机算法设计与分析期终考试复习题
- 银行家算法课程设计
- 第8课时-§1.3算法案例--辗转相除法与更相减损术
- 算法设计与分析基础习题参考答案
第27卷第10期2010年10月 计算机应用与软件 ComputerApplicationsandSoftware V01.27No.10 Oct.2010 基于蚁群算法求解最大团问题 王会颖耿家礼 (安徽财贸职业学院计算机系安微合肥230 ...
摘 要:由于影响范围的重叠效应,单纯的影响力度量算法并不能解决微博网络中的影响力最大化问题,针对这一研究现状,提出一种用于微博网络中TopK节点挖掘的算法GABE.通过归纳决定微博用户影响力的关键因素,提出了节点间影响率的概念,进而建立了用 ...
数据挖掘十大经典算法 一. C4.5 C4.5算法是机器学习算法中的一种分类决策树算法, 其核心算法是ID3 算 法. C4.5算法继承了ID3算法的优点,并在以下几方面对ID3算法进行了改进: 1) 用信息增益率来选择属性,克服了用信息增 ...
摘 要:针对K均值聚类(KMC)算法全局搜索能力差.初始聚类中心选择敏感,以及原始人工蜂群(ABC)算法的初始化随机性.易早熟.后期收敛速度慢等问题,提出了一种改进人工蜂群算法(IABC).该算法利用最大最小距离积方法初始化蜂群,构造出适应 ...
贪心算法思想 顾名思义,贪心算法总是作出在当前看来最好的选择.也就是说贪心算法并不从整体最优考虑,它所作出的选择只是在某种意义上的局部最优选择.当然,希望贪心算法得到的最终结果也是整体最优的.虽然贪心算法不能对所有问题都得到整体最优解,但对 ...
第6卷 第3期太原师范学院学报(自然科学版) 2007年9月 JO U R NA L O F T A IY U A N N OR M A L U NI VER SIT Y (N atur al Science Editio n) Sept. ...
计算机算法设计与分析复习题 一.填空题 1.一个算法复杂性的高低体现在计算机运行该算法所需的时间和存储器资源上,因此算法的复杂性有 时间 复杂性和空间复杂性之分. 2.出自于"平衡子问题"的思想,通常分治法在分割原问题, ...
操作系统课程设计报告 题目:银行家算法 安全性算法 院 (系):计算机科学与工程 专 业:软件工程 班 级:130608班 学 生:姚骏川 学 号:130608118 指导教师:姜虹 2015年12月28 目录 摘 要 .......... ...
课题:§1.3算法案例--辗转相除法与更相减损术 教学目标: 知识与能力:理解辗转相除法与更相减损术中蕴含的数学原理,并能根据这些原理进行算法分析:基本能根据算法语句与程序框图的知识设计完整的程序框图并写出算法程序. 过程与方法:在辗转相除 ...
习题 1.1 5..证明等式 gcd(m,n)=gcd(n,m mod n)对每一对正整数 m,n 都成立. Hint: 根据除法的定义不难证明: 如果 d 整除 u 和 v, 那么 d 一定能整除 u±v; 如果 d 整除 u,那么 d ...