- 浏览: 32912 次
最新评论
#include<stdio.h>
#define MAX 100001
struct str
{
int nFrom;
int nTo;
int nSum;
};
str getMax(int nData[],int n);
void vPutOut(str A);
str get3Parts(int nData[],int left,int right);
str getMid(int nData[],int left,int mid,int right);
int main()
{
int nData[MAX];
int i,n;
str A;
scanf("%d",&n);
for(i=1;i<=n;i++)
{
scanf("%d",&nData[i]);
}
A=getMax(nData,n);
vPutOut(A);
return 0;
}
str getMax(int nData[],int n)
{
str B;
B=get3Parts(nData,1,n);
return B;
}
void vPutOut(str A)
{
printf("FROM=%d,TO=%d\n",A.nFrom,A.nTo);
printf("SUM=%d\n",A.nSum);
}
str get3Parts(int nData[],int left,int right)
{
str B;
str Bleft,Bright,Bmid;
int from,to,mid;
int nSum,leftSum,rigthSum,midSum;
nSum=0;
left=0;
right=0;
if(left==right)
{
if(nData[left]>0)
{
from=left;
to=left;
nSum=nData[left];
}
}
else
{
mid=(left+right)/2;
Bleft=get3Parts(nData,left,mid);
leftSum=Bleft.nSum;
Bright=get3Parts(nData,mid+1,right);
rigthSum=Bright.nSum;
Bmid=getMid(nData,left,mid,right);
midSum=Bmid.nSum;
if((leftSum>rigthSum)&&(leftSum>midSum))
{
nSum=leftSum;
from=Bleft.nFrom;
to=Bleft.nTo;
}
else
{
if(rigthSum>midSum)
{
nSum=rigthSum;
from=Bright.nFrom;
to=Bright.nTo;
}
else
{
nSum=midSum;
from=Bmid.nFrom;
to=Bmid.nTo;
}
}
}
B.nSum=nSum;
B.nFrom=from;
B.nTo=to;
return B;
}
str getMid(int nData[],int left,int mid,int right)
{
str B;
int from,to;
int nSum,s1,s2;
int i;
from=mid;
to=mid;
nSum=0;
s1=0;
for(i=mid;i<=left;i--)
{
nSum+=nData[i];
if(nSum>s1)
{
s1=nSum;
from=i;
}
}
nSum=0;
s2=0;
for(i=mid;i<=right;i++)
{
nSum+=nData[i];
if(nSum>s2)
{
s2=nSum;
to=i;
}
}
nSum=s1+s2;
B.nFrom=from;
B.nTo=to;
B.nSum=nSum;
return B;
}
#define MAX 100001
struct str
{
int nFrom;
int nTo;
int nSum;
};
str getMax(int nData[],int n);
void vPutOut(str A);
str get3Parts(int nData[],int left,int right);
str getMid(int nData[],int left,int mid,int right);
int main()
{
int nData[MAX];
int i,n;
str A;
scanf("%d",&n);
for(i=1;i<=n;i++)
{
scanf("%d",&nData[i]);
}
A=getMax(nData,n);
vPutOut(A);
return 0;
}
str getMax(int nData[],int n)
{
str B;
B=get3Parts(nData,1,n);
return B;
}
void vPutOut(str A)
{
printf("FROM=%d,TO=%d\n",A.nFrom,A.nTo);
printf("SUM=%d\n",A.nSum);
}
str get3Parts(int nData[],int left,int right)
{
str B;
str Bleft,Bright,Bmid;
int from,to,mid;
int nSum,leftSum,rigthSum,midSum;
nSum=0;
left=0;
right=0;
if(left==right)
{
if(nData[left]>0)
{
from=left;
to=left;
nSum=nData[left];
}
}
else
{
mid=(left+right)/2;
Bleft=get3Parts(nData,left,mid);
leftSum=Bleft.nSum;
Bright=get3Parts(nData,mid+1,right);
rigthSum=Bright.nSum;
Bmid=getMid(nData,left,mid,right);
midSum=Bmid.nSum;
if((leftSum>rigthSum)&&(leftSum>midSum))
{
nSum=leftSum;
from=Bleft.nFrom;
to=Bleft.nTo;
}
else
{
if(rigthSum>midSum)
{
nSum=rigthSum;
from=Bright.nFrom;
to=Bright.nTo;
}
else
{
nSum=midSum;
from=Bmid.nFrom;
to=Bmid.nTo;
}
}
}
B.nSum=nSum;
B.nFrom=from;
B.nTo=to;
return B;
}
str getMid(int nData[],int left,int mid,int right)
{
str B;
int from,to;
int nSum,s1,s2;
int i;
from=mid;
to=mid;
nSum=0;
s1=0;
for(i=mid;i<=left;i--)
{
nSum+=nData[i];
if(nSum>s1)
{
s1=nSum;
from=i;
}
}
nSum=0;
s2=0;
for(i=mid;i<=right;i++)
{
nSum+=nData[i];
if(nSum>s2)
{
s2=nSum;
to=i;
}
}
nSum=s1+s2;
B.nFrom=from;
B.nTo=to;
B.nSum=nSum;
return B;
}
发表评论
-
最大子段和
2012-01-05 13:59 782给出N个数字, 计算出最大的子段和。 Input 第一行给 ... -
最长不下降子序列长度
2012-01-05 13:55 1315对于序列(1, 7, 3, 5, 9, 4,,有它的一些不下降 ... -
求两字符串匹配的最长子序列
2012-01-05 13:52 1020如果两种特征序列的公共子序列越长表示越接近,现在请你帮助计算出 ... -
编辑距离问题
2012-01-05 13:48 661#include<iostream> #incl ... -
Kruskal最小生成树
2011-12-08 14:26 707#include<iostream> #inclu ... -
prime
2011-12-01 20:09 616#include<iostream> using ... -
哈弗曼编码
2011-11-28 10:43 1#include<iostream> #defi ... -
哈弗曼编码
2011-11-28 10:42 526#include<iostream> #defi ... -
#贪心算法(零件加工)
2011-10-27 13:25 987#include<stdio.h> #includ ... -
众数问题
2011-10-20 14:57 793#include <stdio.h> #inclu ... -
输油管道问题
2011-10-13 14:45 602#include <stdio.h> #inclu ... -
幂的精确求值
2011-09-22 15:07 463#include<iostream> using ... -
大数加法
2011-09-22 12:56 613#include<iostream> #incl ... -
三姐妹之出题
2011-09-15 14:15 666#include<iostream> #incl ... -
最大子段和问题(O(N^2))
2011-09-08 15:04 610#include<stdio.h> int a[ ... -
最大子段和问题(O(N^3))
2011-09-08 14:45 481#include<stdio.h> int a[ ...
相关推荐
最近对问题 最大子段和(分治法) 最长公共子序列问题 最大子段和(动态规划)
1.用分治算法求解最大子段和问题。要求算法的时间复杂度不超过O(nlogn)。 最大子段和问题描述:给定由n个整数(可能为负整数)组成的序列a1, a2,…, an, 求该序列形如的子段和的最大值。当所有整数均为负整数时...
用分治法求最大子段和,适合刚接触数据结构的初学者
算法设计与分析中最大子段和问题的蛮力法、分治法和动态规划法
最大子段和分治法源程序和ppt 非常的经典,但不是一般人能随随便便想得到的 (C语言源程序),希望大家下载给我加点分啦。
【问题描述】使用分治递归算法解最大子段和问题,具体来说就是,将序列分为长度相等的左右两段,分别求出这两段的最大子段和,包含左右部分子段的最大子段和,求这三种情况得到的最大子段和的最大值。 【输入形式】...
/* 分治法思想:将一个n规模的问题分解成k个规模较小的子问题,并且这些子问题 之间都是相互独立的,通过递归求解这些子问题,然后将子问题的解合并,就可以 得到原问题的解。
算法设计实验报告,包括:蛮力法、分治法和减治法求最大子段和问题各自的基本思想、时间复杂度分析,C++实现代码,三种算法运行时间的比较,运行截图,实验心得。
蛮力法、分治法和动态规划法设计最大子段和问题的算法,一、试分别利用蛮力法、分治法和动态规划法求解最大子段和问题,要求写出C/C++程序实现和算法的效率分析。程序运行结果要同时给出最大子段和的值以及由哪个子段...
用蛮力法,分治法,动态规划法求最大子段和问题
B_(HDU_1231)(最大子段和,分治).cpp
本算法是用C++实现最大子段和问题,包括蛮力法,分治法和动态规划法的实现及时间效率的对比
算法最大子段和问题,蛮力法,分治法,动态规划法
实验目的 (1)掌握分治法的设计思想; (2)学会应用分治法解决问题; 设计算法解决最大子段和或棋盘覆盖问题 实验环境 Win7 DevCPP
【问题描述】使用分治递归算法解最大子段和问题,具体来说就是,将序列分为长度相等的左右两段,分别求出这两段的最大子段和,包含左右部分子段的最大子段和,求这三种情况得到的最大子段和的最大值。 【输入形式】...
用动态规划法和分治法 自己写的 可以运行
最大子段和/三种方法/c++语言/(内有报告) 蛮力法,动态规划法,分治法。 可比较时间,随机输入数据......
解决方案+文档说明,使用动态规划思想解决最大子段和问题
分别用蛮力法、分治法、动态规划法设计的最大子段和问题的算法。用VC++ 6.0运行。