给定由n个整数组成的序列(a1, a2, …, an),求该序列的子段和的最大值,当所有整数均为负整数时,其最大子段和为0。
LargestSubsegmentSum1.java //蛮力算法
import java.util.*;
public class LargestSubsegmentSum1
{
public static void main(String[] args)
{
/**
*从键盘输入所要求的序列的长度n
*/
Scanner in=new Scanner(System.in);
System.out.println("Please enter the length of segment you want to make(输入你要求的序列的长度):");
int n=in.nextInt();
/**
*从键盘输入所要求的序列,存储在a[n]中
*/
int[] a=new int[n];
System.out.println("Now,please enter the elements of the segment you want(现在请依次输入这个序列包含的元素(整数)):");
for(int i=0;i<n;i++)
{
a[i]=in.nextInt();
}
double startTime=System.currentTimeMillis();//starttime
/**
*求解最大子段和存在maxSum中
*/
int maxSum=a[0];
for(int i=0;i<n-1;i++)
{
int temp=a[i];
for(int j=i+1;j<n;j++)
{
temp+=a[j];
if(temp>maxSum)
maxSum=temp;
}
}
double endTime=System.currentTimeMillis();//endtime
/**
*打印输出求解结果和程序所用时间
*/
System.out.println("The largest sub-segment sum is(最大子段和是):"+maxSum);
System.out.println("Basic Statements take(基本语句用时) "+(endTime-startTime)+" milliseconds!");
}
}
***************************************************************************
分治算法描述:
int MaxSum(int a[ ], int left, int right)
{
sum=0;
if (left= =right) { //如果序列长度为1,直接求解
if (a[left]>0) sum=a[left];
else sum=0;
}
else {
center=(left+right)/2; //划分
leftsum=MaxSum(a, left, center);
//对应情况①,递归求解
rightsum=MaxSum(a, center+1, right);
//对应情况②,递归求解
s1=0; lefts=0; //以下对应情况③,先求解s1
for (i=center; i>=left; i--)
{
lefts+=a[i];
if (lefts>s1) s1=lefts; }
s2=0; rights=0; //再求解s2
for (j=center+1; j<=right; j++)
{
rights+=a[j];
if (rights>s2) s2=rights; }
sum=s1+s2; //计算情况③的最大子段和
if (sum<leftsum) sum=leftsum;
//合并,在sum、leftsum和rightsum中取较大者
if (sum<rightsum) sum=rightsum; }
return sum; }
LargestSubsegmentSum2.java //分治算法
import java.util.*;
public class LargestSubsegmentSum2
{
public static void main(String[] args)
{
/**
*从键盘输入所要求的序列的长度n
*/
Scanner in=new Scanner(System.in);
System.out.println("Please enter the length of segment you want to make(输入你要求的序列的长度):");
int n=in.nextInt();
/**
*从键盘输入所要求的序列,存储在a[n]中
*/
int[] a=new int[n];
System.out.println("Now,please enter the elements of the segment you want(现在请依次输入这个序列包含的元素(整数)):");
for(int i=0;i<n;i++)
{
a[i]=in.nextInt();
}
/**
*调用函数MaxSum()求解出结果
*/
double startTime=System.currentTimeMillis();//starttime
int maxSum=MaxSum(a,0,n);
double endTime=System.currentTimeMillis();//endtime
/**
*打印输出结果和程序运行所用时间
*/
System.out.println("The largest sub-segment sum is(最大子段和是):"+maxSum);
System.out.println("Basic Statements take(基本语句用时) "+(endTime-startTime)+" milliseconds!");
}
/**
*设计求解最大子段和的函数MaxSum()
*/
public static int MaxSum(int[] a,int left,int right)
{
int maxSum=0;
if(left==right)
{
if(a[0]>0)
maxSum=a[0];
}
else
{
int center=(left+right)/2;
int maxSum1=MaxSum(a,left,center);
int maxSum2=MaxSum(a,center+1,right);
int s1=0;
int lefts=0;
for(int i=center;i>=left;i--)
{
lefts+=a[i];
if(lefts>s1)
s1=lefts;
}
int s2=0;
int rights=0;
for(int j=center+1;j<right;j++)
{
rights+=a[j];
if(rights>s2)
s2=rights;
}
maxSum=s1+s2;
if(maxSum<maxSum1)
maxSum=maxSum1;
if(maxSum<maxSum2)
maxSum=maxSum2;
}
return maxSum;
}
}
***********************************************************************************************
LargestSubsegmentSum3.java //动态规划算法
import java.util.*;
public class LargestSubsegmentSum3
{
public static void main(String[] args)
{
/**
*从键盘输入所要求的序列的长度n
*/
Scanner in=new Scanner(System.in);
System.out.println("Please enter the length of segment you want to make(输入你要求的序列的长度):");
int n=in.nextInt();
/**
*从键盘输入所要求的序列,存储在a[n]中
*/
int[] a=new int[n];
System.out.println("Now,please enter the elements of the segment you want(现在请依次输入这个序列包含的元素(整数)):");
int i;
for(i=0;i<n;i++)
{
a[i]=in.nextInt();
}
/**
*求解最大子段和存在maxSum中
*/
double startTime=System.currentTimeMillis();//starttime
int maxSum=0;
int[] b=new int[n];
b[0]=0;
for(int j=1;j<n;j++)
{
if(b[j-1]>0)
b[j]=b[j-1]+a[j];
else
{
b[j]=a[j];
i=j;
}
}
for(int j=0;j<n;j++)
{
if(b[j]>maxSum)
maxSum=b[j];
}
double endTime=System.currentTimeMillis();//endtime
/**
*打印输出结果和程序运行所用时间
*/
System.out.println("The largest sub-segment sum is(最大子段和是):"+maxSum);
System.out.println("Basic Statements take(基本语句用时) "+(endTime-startTime)+" milliseconds!");
}
}
本文来自CSDN博客,转载请标明出处:http://blog.csdn.net/wanbingglass/archive/2009/12/22/5057194.aspx
分享到:
相关推荐
1.用分治算法求解最大子段和问题。要求算法的时间复杂度不超过O(nlogn)。 最大子段和问题描述:给定由n个整数(可能为负整数)组成的序列a1, a2,…, an, 求该序列形如的子段和的最大值。当所有整数均为负整数时...
求最大子段和
算法设计实验报告,包括:蛮力法、分治法和减治法求最大子段和问题各自的基本思想、时间复杂度分析,C++实现代码,三种算法运行时间的比较,运行截图,实验心得。
【问题描述】使用分治递归算法解最大子段和问题,具体来说就是,将序列分为长度相等的左右两段,分别求出这两段的最大子段和,包含左右部分子段的最大子段和,求这三种情况得到的最大子段和的最大值。 【输入形式】...
最大子段和问题,可参考《算法设计与分析》讲义中关于用动态规划策略求解最大子段和问题的思想设计动态规划算法。本算法用户需要输入元素个数n,及n个整数。程序应该给出良好的用户界面,输出最大子段相关信息,包括...
最近对问题 最大子段和(分治法) 最长公共子序列问题 最大子段和(动态规划)
实验目的 (1)掌握分治法的设计思想; (2)学会应用分治法解决问题; 设计算法解决最大子段和或棋盘覆盖问题 实验环境 Win7 DevCPP
这是一个java代码,用于求解最大字段和的问题
算法最大子段和问题,蛮力法,分治法,动态规划法
带输入输出界面的最大子段和问题 用java编写的
C 最大子段和问题的各种算法具体实现!经典算法!
分形算法与程序设计——Java实现 分形算法与程序设计——Java实现
分别用蛮力法、分治法、动态规划法设计的最大子段和问题的算法。用VC++ 6.0运行。
算法设计与分析中最大子段和问题的蛮力法、分治法和动态规划法
【问题描述】使用分治递归算法解最大子段和问题,具体来说就是,将序列分为长度相等的左右两段,分别求出这两段的最大子段和,包含左右部分子段的最大子段和,求这三种情况得到的最大子段和的最大值。 【输入形式】...
实现运筹学中线性规划算法的Java程序,包含LP类和Main类,Main类支持控制台实时输入线性规划问题参数,LP类实现线性规划问题中的标准化,添加人工变量,两阶段法等步骤
用蛮力法,分治法,动态规划法求最大子段和问题
蛮力法、分治法和动态规划法设计最大子段和问题的算法,一、试分别利用蛮力法、分治法和动态规划法求解最大子段和问题,要求写出C/C++程序实现和算法的效率分析。程序运行结果要同时给出最大子段和的值以及由哪个子段...
这个是本人在最算法分析实验之最大子段问题时用c#在visual studio 2005上写的一个小程序,能在可视化界面中输入序列,自动生成对应的最大子段。