最大子序列和问题之算法优化

算法一:穷举式地尝试所有的可能

int maxSubsequenceSum(const int a[], int n) { int i, j, k; int thisSum, maxSum = 0; for (i = 0; i < n; i++) for (j = i; j < n; j++) { thisSum = 0; for (k = i; k < j; k++) thisSum += a[k]; if (thisSum > maxSum) maxSum = thisSum; } return maxSum; }

算法复杂度为O(n^3)(三重for循环)


算法二:算法一的改进

int maxSubsequenceSum(const int a[], int n) { int i, j; int thisSum, maxSum = 0; for (i = 0; i < n; i++) { thisSum = 0; for (j = i; j < n; j++) { thisSum += a[j]; if (thisSum > maxSum) maxSum = thisSum; } } return maxSum; }

该算法去除了算法一中不必要的计算,时间复杂度为O(n^2)(两重for循环)。


算法三:分治(divide-and-conquer)策略

分治策略:

分:把问题分成若干个(通常是两个)规模相当的子问题,然后递归地对它们求解。

治:将若干个问题的解4合并到一起并可能再做少量的附加工作,最后得到整个问题的解。

在这个问题中,最大子序列和可能在三处出现:即左半部序列、右半部序列、穿过中部从而占据左右两半部分的序列。前两种情况可以通过递归求解。而递归的基准情况(base cases)是序列只有一个元素(left == right),若该元素大于0,则返回该元素,否则返回0。第三种情况的最大和可以通过分别求出左边部分(包含左半部分最后一个)的最大和以及右边部分(包含右边部分的第一个)的最大和,再将它们相加得到。

int maxSubsequenceSum(const int a[], int left, int right) { int i, mid, maxLeftSum, maxRightSum; int maxLeftBorderSum, leftBorderSum; int maxRightBorderSum, rightBorderSum; if (left == right) { /*基准情况*/ if (a[left] >= 0) return a[left]; else return 0; } mid = left + (right - left) / 2; maxLeftSum = maxSubsequenceSum(a, left, mid); /*左半部分的最大和*/ maxRightSum = maxSubsequenceSum(a, mid+1, right); /*右半部分的最大和*/ /*下面求穿过中点的最大和*/ maxLeftBorderSum = 0, leftBorderSum = 0; for (i = mid; i >= left; i--) /*中点及其以左的最大和*/ { leftBorderSum += a[i]; if (leftBorderSum > maxLeftBorderSum) maxLeftBorderSum = leftBorderSum; } maxRightBorderSum = 0, rightBorderSum = 0; for (i = mid+1; i <= right; i++) /*中点以右的最大和*/ { rightBorderSum += a[i]; if (rightBorderSum > maxRightBorderSum) maxRightBorderSum = rightBorderSum; } /*返回三部分中的最大值*/ return max3(maxLeftSum, maxRightSum, maxLeftBorderSum+maxRightBorderSum); } int max3(int a, int b, int c) { int maxNum = a; if (b > maxNum) maxNum = b; if (c > maxNum) maxNum = c; return maxNum; }

以序列2,4,-1,-5,4,-1为例,其左半部分最大和为2 + 4 = 6;右半部分最大和为4,穿过中心的最大和为(-1 + 4 + 2)+ (-5 + 4)= 0。故该序列的最大子序列和为max(6,4,0)= 6。 时间复杂度分析: 假设T(n)为求解大小为n的最大子序列和问题所花费的时间。当n = 1是,T(1) = O(1);当n > 1时,两次递归花费的总时间为2T(n/2),两个并列的for循环花费的时间是O(len(left)+len(right)) = O(n),一共为2T(n/2)+O(n)。综上可列如下方程组:

T(1) = 1 T(n) = 2T(n/2) + O(n)

事实上,上述方程组常常通用于分治算法,由方程组可算出T(n) = O(nlogn)。


算法四:

算法三利用递归较好的解决了最大子序列和问题,但仔细分析,在递归过程中,同一个元素很可能多次被操作,有没有更高效的算法?先上代码

int maxSubsequenceSum(const int a[], int n) { int i; int maxSum, thisSum; maxSum = thisSum = 0; for (i = 0; i < n; i++) { thisSum += a[i]; if (thisSum > maxSum) maxSum = thisSum; else if (thisSum < 0) thisSum = 0; } return maxSum; }

可以简单的分析出上述代码的时间复杂度是O(n),比前三种都高效。它为什么是正确的?从直观上理解:首先for循环的if语句保证了每次更新后最大和保存在maxSum中,而我们从i = 0开始扫描,假设扫描到i = t(t < n),且此时的最大和已经保存在maxSum中,而当前的和(thisSum)如果大于0,不管当i > t的元素大小如何,加上thisSum总会使之后的和变大,而如果thisSum小于0,肯定会使之后的和变小,既然还会变小,那干脆就重新来过(thisSum = 0),有些另起炉灶的意味。


该算法一个附带的优点是,它只对数据进行一次的扫描,一旦a[i]被读入并被处理,它就不再需要记忆。因此,如果数组在磁盘或磁带上,它就可以被顺序读入,在主存中不必储存数组的任何部分。不仅如此,在任意时刻,该算法都能对它已经读入的数据给出子序列问题的正确答案(其他算法即前三种不具有这个特性)。具有这种特性的算法叫做联机算法(online algorithm)。仅需要常量空间并以线性时间运行的online algorithm几乎是完美的算法。————《数据结构与算法分析》(中文版第二版)

原文发布于微信公众号 - Spark学习技巧(bigdatatip)

原文发表时间:2018-05-06

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏闪电gogogo的专栏

压缩感知重构算法之正则化正交匹配追踪(ROMP)

  在看代码之前,先拜读了ROMP的经典文章:Needell D,VershyninR.Signal recovery from incompleteand i...

37360
来自专栏WD学习记录

n-gram

N-Gram是大词汇连续语音识别中常用的一种语言模型,对中文而言,我们称之为汉语语言模型(CLM, Chinese Language Model)。汉语语言模型...

13430
来自专栏人工智能LeadAI

决策树会有哪些特性?

决策树(Decision Tree)是机器学习中最常见的算法, 因为决策树的结果简单,容易理解, 因此应用超级广泛, 但是机器学习的专家们在设计决策树的时候会考...

38870
来自专栏数据科学与人工智能

【算法】利用文档-词项矩阵实现文本数据结构化

“词袋模型”一词源自“Bag of words”,简称 BOW ,是构建文档-词项矩阵的基本思想。对于给定的文本,可以是一个段落,也可以是一个文档,该模型都忽略...

45170
来自专栏Leetcode名企之路

【Leetcode】64. 最小路径和

给定一个包含非负整数的 m x n 网格,请找出一条从左上角到右下角的路径,使得路径上的数字总和为最小。

30010
来自专栏ml

数据挖掘之聚类算法K-Means总结

序   由于项目需要,需要对数据进行处理,故而又要滚回来看看paper,做点小功课,这篇文章只是简单的总结一下基础的Kmeans算法思想以及实现; 正文:   ...

40780
来自专栏小鹏的专栏

Tensorflow使用的预训练的resnet_v2_50,resnet_v2_101,resnet_v2_152等模型预测,训练

tensorflow 实现:Inception,ResNet , VGG , MobileNet, Inception-ResNet; 地址: https:/...

1.2K80
来自专栏Petrichor的专栏

tensorflow: bn层

可视化 batch normalization 过程中的 tensor演化(以输入一张[1, 4 , 4, 1]的图片为例)

56640
来自专栏深度学习与计算机视觉

算法-从1,...,99,2015这100个数中任意选择若干个数(可能为0个数)求异或,试求异或的期望值

题目: 从1,2,3,…..98,99,2015这100个数中任意选择若干个数(可能为0个数)求异或,试求异或的期望值。 解题思路: 这是阿里巴巴的...

293100
来自专栏小小挖掘机

使用Seq2Seq+attention实现简单的Chatbot

本文代码的github连接:https://github.com/princewen/tensorflow_practice/tree/master/chat_...

4K60

扫码关注云+社区

领取腾讯云代金券