本文使用分治思想求解一个整型数组中的最大子序列,该算法的时间复杂度为NlogN,使用千万级的数据量计算结果的时间不超过0.5s。该算法使用了分治的思想:求解最大子序列的问题可以理解为将整个数组分成左右两部分,分别求解左边和 右边的最大子序列,并且还有一种情况是最大子序列在中间,此时可以可以直接从中间开始分别向左和向右遍历求解左右两边的最大子序列(由于此时假定最大子序列在中间,因而中间的元素肯定在最大子序列中),然后将两边的最大子序列相加就会得到最大子序列在中间时的子序列,此时当前数组就会有三个(左边,右边和中间)已经求得的最大子序列,现只需要比较这三个子序列的和即可,将最大和返回。具体的算法如下:
public class Solution { public long findMaxSubSequence(Integer[] arr) { // return maxSumRec(arr, 0, arr.length - 1); } // 求解最大子序列函数 private long maxSumRec(Integer[] arr, int left, int right) { // 递归调用的出口 if (left == right) { return arr[left]; } // 分别计算左边和右边的最大子序列 int center = (left + right) / 2; long maxLeftSum = maxSumRec(arr, left, center); long maxRightSum = maxSumRec(arr, center + 1, right); // 计算中间的最大子序列的左半部分的最大值 int maxLeftBorderSum = 0, leftBorderSum = 0; for (int i = center; i >= left; i--) { leftBorderSum += arr[i]; if (leftBorderSum > maxLeftBorderSum) { maxLeftBorderSum = leftBorderSum; } } // 计算中间的最大子序列的右半部分的最大值 int maxRightBorderSum = 0, rightBorderSum = 0; for (int i = center + 1; i <= right; i++) { rightBorderSum += arr[i]; if (rightBorderSum > maxRightBorderSum) { maxRightBorderSum = rightBorderSum; } } return max(maxLeftSum, maxRightSum, maxLeftBorderSum + maxRightBorderSum); } // 求解三个值中的最大值 private long max(long maxLeftSum, long maxRightSum, int maxBorderSum) { return maxLeftSum >= maxRightSum && maxLeftSum >= maxBorderSum ? maxLeftSum : (maxRightSum > maxBorderSum ? maxRightSum : maxBorderSum); } }
具体的实验程序如下:
import java.util.Date; import java.util.Random; public class App { public static void main(String[] args) { Integer[] arr = new Integer[10000000]; for (int i = 0; i < 10000000; i++) { arr[i] = new Random().nextInt(); } Solution solution = new Solution(); Long start = new Date().getTime(); long result = solution.findMaxSubSequence(arr); Long end = new Date().getTime(); System.out.println("结果为:" + result); System.out.print("所用时长为:" + (end - start)); } }
运行结果如下:
计算结果为:2147483164 所用时长为:447 Process finished with exit code 0
这是计算最大子序列的一种算法,现贴出一种更为完美的方法,其时间复杂度为O(N),代码量也得到了大大的简化,代码如下:
public class Solution { public long findMaxSubSequence(Integer[] arr) { long maxSum = 0, thisSum = 0; for (int i = 0; i < arr.length; i++) { thisSum += arr[i]; if (thisSum > maxSum) { maxSum = thisSum; } else if (thisSum < 0){ thisSum = 0; } } return maxSum; } }
由于本人也不甚理解,现只将代码帖于此处。
相关推荐
自己写的分治算法,也包括了暴力求解的部分,并比较两者的运行时间,输出最大子数组的起始位置
2.采用分治法求解最大连续子序列和问题 给定一个有n(n≥1)个整数的序列,要求求出其中最大连续子序列的和。 例如: 序列(-2,11,-4,13,-5,-2)的最大子序列和为20序列; (-6,2,4,-7,5,3,2,-1,6,...
数据结构的分治法求解最大值,数据结构的分治法求解最大值
1.用分治算法求解最大子段和问题。要求算法的时间复杂度不超过O(nlogn)。 最大子段和问题描述:给定由n个整数(可能为负整数)组成的序列a1, a2,…, an, 求该序列形如的子段和的最大值。当所有整数均为负整数时...
本文件为分治法求解最大子数组的测试数据,每行为一个数字,共666665个数字,数字包含正数、负数和零,用于求解的原始数组应以本文件的行号为序进行构建。完整代码详见文章...
利用分治法求解空中飞行管理问题,陈思源,陈杰,分治法是一种常用的问题求解方法,可以化简问题规模,降低计算复杂度。飞行管理问题实质上属于搜索问题,利用常规方法可以解决,
文件给出了四种方式求解子序列的最大和,并给出了具体的代码实现。对于深入探讨算法和程序性能非常有帮助。
最近对问题 最大子段和(分治法) 最长公共子序列问题 最大子段和(动态规划)
动态规划算法与分治法类似,其基本思想也是将待求解问题分解成若干子问题,先求解子问题,然后从这些子问题的解求得原问题的解。与分治法不同的是,适合于动态规划法求解的问题,经分解求得的子问题往往不是互相独立...
分治法求解序列最大最小元素【算法设计与分析】
一个整数数组中的元素有正有负,在该数组中找出一个连续子数组,要求该连续子数组中各元素的和最大,这个连续子数组便被称作最大连续子数组。 随机产生1000以上的数据(有正有负),写入文件input.txt 比如数组{2,4,...
序列Z=,C,D,B>是序列X=,B,C,B,D,A,B>的子序列,相应的递增下标序列为,3,5,7>。 一般地,给定一个序列X=,x2,…,xm>,则另一个序列Z=,z2,…,zk>是X的子序列,是指存在一个严格递增的下标序列〈i1,i2,…,...
用分治法求最大子段和,适合刚接触数据结构的初学者
C语言分治算法求解30枚银币中的某枚假币,简单而言,30枚银币中有1枚假币,该假币的重量比其他29枚银币的重量小1,先将30枚银币平分成两部分,各15枚,分别称重,重量小的那一半银币中必然包含假币,然后再分成两...
全都是自己写的,都能跑出来 实打实写的哦~ 实现分治法求解棋盘问题算法
动态规划算法与分治法类似,其基本思想也是将待求解问题分解成若干个子问题,先求解子问题,然后从这些子问题的解得到原问题的解。 与分治法不同的是,适合于用动态规划法求解的问题,经分解得到的子问题往往不是独立...
利用分治法求解凸包问题!c语言 #include #define PPmax 30 #define random(x) (rand()%x) typedef struct node{ float x,y; }Point; Point DingDian[PPmax];//用于存放凸边形的顶点 int DingDnum=0; typedef ...
1. 设计程序利用分治策略求n个数的最大值和最小值。 2. 利用分治策略,在n个不同元素中找出第k个最小元素。
治法是一种常用的问题求解方法,可以简化问题规模,降低计算复杂 度。飞行管理问题实质上属于搜索问题,利用常规方法解决时间耗费大,而利用分 治法可以得到很好的解决。
用分治法的思想去求解最大值。