最大子序列和O(N)算法简单分析『神兽必读』

对于一个全为负数的序列,最长公共子序列的和值应该是0,理由在于,由0个整数所组成的空子序列也是一个子序列——最大子序列和问题从O(N^3)到线性的算法

其他情况大家也能理解了。 先看算法,算法来自《数据结构与算法分析——C语言描述》

int
MaxSubsequenceSum(const int A[], int N)
{
    int ThisSum, MaxSum, j;
    for(j = 0; j < N; j++) /*1*/
    {
        ThisSum += A[j];   /*2*/
        
        if(ThisSum > MaxSum) /*3*/
            MaxSum = ThisSum; /*4*/
        else if(ThisSum < 0) /*5*/
            ThisSum = 0;   /*6*/
    }
    
    return MaxSum;
}

可以看到算法中重要的位置都标注出来了。 显然这个算法有一个for循环,整体时间复杂度可以看作O(N)。 就算法正确性来分析,首先假设这样的输入:-2, -3, 5, 6, -1, 8, 9

  1. 扫描到-2或-3的时候,执行/*2*/,/*5*/条件成立,所以执行/*6*/,此时ThisSum依然是0,MaxSum也是0

为什么不把开头的负数也加和到最大子序列的和中去呢,显然我们做一个假设就很明显了,如-1, 1, 2, 3, 4, 5,没有开头的-1结果更大。

  1. 继续扫描5, 6,执行/*2*/,/*3*/条件成立,所以执行/*4*/,此时ThisSum是11,MaxSum也是11
  2. 继续扫描到-1,执行/*2*/,ThisSum变成了10,此时条件/*3*/和/*5*/都不成立,所以MaxSum仍然是11,只不过ThisSum变小了
  3. 继续扫描到8,执行/*2*/,ThisSum变成18,此时条件/*3*/成立,执行/*4*/,MaxSum从上一次结果的11变成18。
  4. 依此类推

我想这个分析就到此结束了。


UPDATE 或许你会想到了,有时候最大子序列和是某一小段的话,比如是后半段,但是这个算法明显给人的感觉就是一路加和过来呀,好像是认为越长的子序列和越大呀?!这里继续做一个假设:5, 6,-2, -3,-1, -7,8, 9 明显最大的子序列是8,9,中间跨度的那些负数都不应该加起来,这样的想法的确是对的,但是这个算法也做到了啊。 加和5,6后前面得到的最大的MaxSum一直都是11,而ThisSum才会减少,加上-7时ThisSum会变成-2,此时ThisSum会被修正为0,MaxSum没有改变还是11;接下来ThisSum加上8,9得到的ThisSum是17,要比之前的MaxSum大,所以MaxSum也被替换成17了。

这些说明都比较粗糙,见谅!

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏机器学习算法与Python学习

Numpy

Numpy Numpy是Python中用于科学计算的核心库。它提供了高性能的多维数组对象,以及相关工具。(本文文末的原文链接为numpy的官方文档) NumPy...

35370
来自专栏TensorFlow从0到N

TensorFlow从0到1 - 2 - TensorFlow核心编程

上一篇Hello, TensorFlow!中的代码还未解释,本篇介绍TensorFlow核心编程的几个基本概念后,那些Python代码就很容易理解了。 与Te...

487100
来自专栏landv

c语言_头文件

22630
来自专栏二进制文集

LeetCode 动态规划 题目分类汇总

A robot is located at the top-left corner of a m x n grid (marked 'Start' in the...

40060
来自专栏小二的折腾日记

LeetCode-52-N-Queens-II

只返回N皇后问题结果的种数。 因此不需要每一个字符串置位了,只需要判断一个位置的横竖,斜45度和斜135度方向的值即可。依然采用递归的方式,这里需要注意的是,由...

6110
来自专栏小红豆的数据分析

小蛇学python(18)pandas的数据聚合与分组计算

对数据集进行分组并对各组应用一个函数,这是数据分析工作的重要环节。在将数据集准备好之后,通常的任务就是计算分组统计或生成透视表。pandas提供了一个高效的gr...

29820
来自专栏程序员的知识天地

Python实现随机生成验证码?小菜一碟!

Python随机生成验证码的方法有很多,今天给大家列举两种,大家也可以在这个基础上进行改造,设计出适合自己的验证码方法

16320
来自专栏人工智能LeadAI

TensorFlow从0到1丨第2篇:TensorFlow核心编程

上一篇Hello, TensorFlow!中的代码还未解释,本篇介绍TensorFlow核心编程的几个基本概念后,那些Python代码就很容易理解了。 与Ten...

41240
来自专栏Java爬坑系列

C\C++ 生成各位数不相等的随机数

  最近想写一个1A2B的小游戏来练习一下,结果在第一步生成随机数的时候就遇到了一点点问题。   游戏初始化时需要先生成一个四位随机数,且各位各不相等。于是最开...

29770
来自专栏人工智能LeadAI

pytorch入门教程 | 第一章:Tensor

1 pytorch安装 安装pytorch之前,需要安装好python,还没安装过python的宝宝请先移步到廖雪峰的python教程,待安装熟悉完之后,再过来...

447100

扫码关注云+社区

领取腾讯云代金券