最大子序列和问题的求解
第一个算法如下,用穷举的方法求出所有的子序列和,返回最大值。
public static int maxSubSumBad(int[] a){
int maxSum=0;
for(int i=0;i<a.length;i++){
int thisSum=0;
for(int j=i;j<a.length;j++){
thisSum+=a[j];
if(thisSum>maxSum)
maxSum=thisSum;
}
}
return maxSum;
}
该算法的时间复杂度为O(N^2),而解决该问题还有更好的办法。可以采用“分治”策略,“分”将问题分为两个大致相等的子问题,然后递归地对其分解;“治”将两个子问题的解附加到一起,最后得到整个问题的解。
在本问题中,最大子序列和可能出现在3处,或整个出现在输入数据的左半部分,或整个出现在输入数据的右半部,或位于输入数据的中部。前两种情况可以递归求解。第三种情况可以求出前半部分的最大和以及后半部分的最大和从而得到。
实现如下:
public static int maxSubSum(int[] a){
return maxSumRec(a,0,a.length-1);
}
private static int maxSumRec(int[] a,int left,int right){
if(left==right){
if(a[left]>0)
return a[left];
else
return 0;
}
int center=(left+right)/2;
int maxLeftSum=maxSumRec(a,left,center);
int maxRightSum=maxSumRec(a,center+1,right);
int maxLeftBorderSum=0,leftBorderSum=0;
for(int i=center;i>=left;i--){
leftBorderSum+=a[i];
if(leftBorderSum>maxLeftBorderSum)
maxLeftBorderSum=leftBorderSum;
}
int maxRightBorderSum=0,rightBorderSum=0;
for(int i=center+1;i<=right;i++){
rightBorderSum+=a[i];
if(rightBorderSum>maxRightBorderSum)
maxRightBorderSum=rightBorderSum;
}
return maxInThree(maxLeftSum,maxRightSum,maxLeftBorderSum+maxRightBorderSum);
}
public static int maxInThree(int first,int second,int third){
int max=0;
if(first>=second)
max=first;
else
max=second;
if(max<third)
max=third;
return max;
}
该方法的时间复杂度为O(NlogN)。而通过思考可以得到结论:如果a[i]是负的,那么它不可能是最有序列的起点,因为任何以a[i]为起点的序列都可以通过以a[i+1]作为起点得到改进。类似地,任何负的子序列不可能是最优子序列的前缀。可以写出如下方法:
public static int maxSubSum2(int[] a){
int maxSum=0,thisSum=0;
for(int i=0;i<a.length;i++){
thisSum+=a[i];
if(maxSum<thisSum)
maxSum=thisSum;
else if(thisSum<0)
thisSum=0;
}
return maxSum;
}
该算法的时间复杂度为O(N),它只对数据进行一次扫描。在任意时刻,算法都能对它已经读入的数据给出正确答案。具有这种特性的算法叫做
联机算法。
分享到:
相关推荐
1. 将矩阵的某一行看成一个序列,设计算法求该序列的最大子序列。 2. 将矩阵相邻两行对应列的元素相加形成一个新的序列,试分析该子序列中每-一个元素的含义,其最大子序列的含义。 3. 设计算法求解该问题,分析样例...
题目是标准的ACM竞赛题,word文档里包含求最大连续子序列的题目和完整的实验代码,并在VC6.0上运行通过!!!
算法设计与分析 最大公共子序列问题 。
动态规划的一个计算两个序列的最长公共子序列的方法如下: 以两个序列 X、Y 为例子: 设有二维数组 f[i,j] 表示 X 的 i 位和 Y 的 j 位之前的最长公共子序列的长度,则有: f[1][1] = same(1,1); f[i,j] = max{f[i-1...
最近对问题 最大子段和(分治法) 最长公共子序列问题 最大子段和(动态规划)
给定一个有n(n≥1)个整数的序列,要求求出其中最大连续子序列的和。 例如: 序列(-2,11,-4,13,-5,-2)的最大子序列和为20序列; (-6,2,4,-7,5,3,2,-1,6,-9,10,-2)的最大子序列和为16。 3.用...
C源程序——两个序列的最大公共子序列#include #include #define MAX 100 char x[MAX+1],y[MAX+1]; int b[MAX+1][MAX+1],c[MAX+1][MAX+1],m,n; static void Init_XY(void); static void LCS_Length(void); static...
C语言C++实现蛮力法求最大子序列和,两种改进方案
3.3 最长公共子序列 3.4 最大子段和 3.5 凸多边形最优三角剖分 3.6 多边形游戏 3.7 图像压缩 3.8 电路布线 3.9 流水作业调度 3.10 0-1背包问题 3.11 最优二叉搜索树 3.12 动态规划加速原理 习题3 第4章 贪心算法 第5...
由于这个问题能运用学过的基本的算法分析和设计的方法与思想,能够锻炼设计较复杂算法的思维,我对这个问题进行了较深入的分析思考,得出了几种复杂度不同算法,并给出了分析和证明。 最长递增子序列问题的描述 设...
假设n为偶数,现在要求将n个数分为两个等规模的集合,s1和s2,使得s1中元素的和减去s2中元素的和的差是最大值,请编写算法并分析时间性能
1. 掌握动态规划法的设计思想并能熟练运用 2. 强化动手编程的能力 二. 实验内容 用动态规划法求两个序列的最大公共子序列 三. 算法思想 1. 分析可得如下动态规划函数: ① L[0][0]=L[i][0]=L...
php //作者:遥远的期待 //QQ:15624575 //算法分析:1、必须是整数序列、2、如果整个序列不全是负数,最大子序列的第一项必须是正数,否则最大子序列后面的数加起来再加上第一项的负数,其和肯定不是最大的;...
求最大字段的三种方法——_动态规划_蛮力_分治算法
算法分析与设计 课程作业 完整版。 包含第二章——递归算法 1.汉诺塔问题 2.斐波纳契数列 3.八皇后问题 第三章——分治算法 1.归并排序 2.快速排序 3.折半查找 4.选择问题 5.最大子段 第四章——贪心算法 1.背包问题...
实验3 最长公共子序列(包括动态规划法) 实验4 最大子段和问题(包括蛮力算法、分治算法和动态规划算法) 实验5 背包、01背包问题(包括贪心算法和分治算法) 实验6 n皇后_2009(包括回溯算法) 以上几个实验基本...
蛮力法、分治法和动态规划法设计最大子段和问题的算法,一、试分别利用蛮力法、分治法和动态规划法求解最大子段和问题,要求写出C/C++程序实现和算法的效率分析。程序运行结果要同时给出最大子段和的值以及由哪个子段...
算法设计与分析中最大子段和问题的蛮力法、分治法和动态规划法
本资源为山东科技大学计算机算法设计与分析的实验报告,分别用暴力...给定n个整数(可能为负整数)组成的序列a1,a2,…,an,求该序列连续的子序列和的最大值。 如果该子段的所有元素和是负整数时定义其最大子段和为0。
最长公共子序列算法利用的算法是( B )。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法 17.实现棋盘覆盖算法利用的算法是( A )。 A、分治法 B、动态规划法 C、贪心法 D、回溯法 18.下面是贪心算法的基本...