最大连续子序列求和（算法）亲测完整C语言代码

左手的ㄟ右手 2022-03-09 12:29 170阅读 0赞

## 最大连续子序列求和（算法）亲测完整C语言代码 ##

> 虽然楼主是一个Java程序员，但是最近在学习的时候，遇到一个问题：最大连续子序列求和。  
> 当时这个问题是个很好的问题，如果理解透彻了，就会很easy。实现的时间复杂度，也很多，非常适合学习研究。

### 一、引入讲解文章 ###

在知乎上有一篇文章讲解了一个理解思路是非常不错的。  
建议用笔和纸写一写画一画，光靠看肯定会很懵。  
[最大连续子序列求和的一种理解思路][Link 1]

### 二、楼主亲测的几种实现方式。 ###

今天后续楼主会把自己的几种实现方式完整的代码贴出来。  
所有算法均已亲测通过，如有疑问，欢迎指出。

#### 1、最慢的一种算法：时间复杂度为T(N)=O(N^3)。 ####

#include <stdio.h>
    
    /*
     * 时间复杂度：T(N) = O(N^3)
     * 输入序列{-2,11,-4,13,-5,-2}
     * 最大子序列：{11,-4,13}和为20
     *
     * 这里首先讲解一下for循环的执行顺序
     * 1、首先int i = 0;
     * 2、然后判断i < 2成立
     * 3、进入循环体打印hello world
     * 4、打印完后i + 1=1
     *
     * 5、判断i < 2 成立
     * 6、进入循环体打印hello world
     * 7、打印完后i + 1 = 2
     *
     * 8、判断i < 2 不成立
     * 9、跳出此循环
     *
     * 至此，共打印了2次hello world
     *
     * for (int i = 0; i < 2; ++i) {
     *      printf("hello world");
     * }
     */
    
    /*
     * N=6
     * 1.
     * 第一次循环：
     * 第一层循环
     * i=0
     *
     * 第二层循环
     * l=i=0
     * ThisSum = 0
     *
     * 第三层循环
     * m=i=0
     * thisSum = A[0]+thisSum
     * thisSum = -2+0=-2
     * 执行完后m=m+1=1
     * 判断
     * thisSum=-2>maxSum 不成立
     * maxSum依然=0
     * 第三层循环继续
     * m=1 l=0 判断m<=l不成立
     * 第三层循环跳出
     *
     * 因为第三层循环体执行完毕，l=l+1=1
     * 继续第二层循环
     * 判断l<N成立，执行第三层循环体，执行出来ThisSum = -2+11=9 MaxSum=0
     * 判断ThisSum > MaxSum 成立 MaxSum = ThisSum = 9
     *
     * 因为第三层循环体执行完毕，l=l+1=2
     * 继续第二层循环
     * 判断l<N成立，执行第三层循环体，执行出来ThisSum = (-2)+11+(-4)=5 MaxSum=9
     * 判断ThisSum > MaxSum 不成立 MaxSum 依然等于 9;
     *
     * 因为第三层循环体执行完毕，l=l+1=3
     * 继续第二层循环
     * 判断l<N成立，执行第三层循环体，执行出来ThisSum = (-2)+11+(-4)+13=18 MaxSum=9
     * 判断ThisSum > MaxSum 成立 MaxSum = ThisSum = 18;
     *
     * 因为第三层循环体执行完毕，l=l+1=4
     * 继续第二层循环
     * 判断l<N成立，执行第三层循环体，执行出来ThisSum = (-2)+11+(-4)+13+(-5)=13 MaxSum=18
     * 判断ThisSum > MaxSum 不成立 MaxSum依然=18;
     *
     * 因为第三层循环体执行完毕，l=l+1=5
     * 继续第二层循环
     * 判断l<N成立，执行第三层循环体，执行出来ThisSum = (-2)+11+(-4)+13+(-5)+(-2)=11 MaxSum=18
     * 判断ThisSum > MaxSum 不成立 MaxSum依然=18;
     *
     * 因为第三层循环体执行完毕，l=l+1=6
     * 继续第二层循环
     * 判断l<N 不成立，跳出第二层循环
     *
     * 2、
     * 因为第二层循环执行完毕了，MaxSum=18。i=i+1=1
     * 判断i<6成立，继续进行第一层循环体
     * l=1,进行第二层循环，与上面的l=0执行过程类似
     * 操作如下：
     * ThisMax=11 > MaxSum=18 不成立 MaxSum依然=18
     * ThisMax=11+(-4)=7 > MaxSum=18 不成立 MaxSum依然=18
     * ThisMax=11+(-4)+13=20 > MaxSum=18 成立 MaxSum=ThisSum=20
     * ThisMax=11+(-4)+13+(-5)=15 > MaxSum=20 不成立 MaxSum依然=20
     * ThisMax=11+(-4)+13+(-5)+(-2)=13 > MaxSum=20 不成立 MaxSum依然=20
     *
     * 3、第一层循环的第3次循环和第2次循环类似
     * 操作如下：
     * ThisMax=-4 > MaxSum=20 不成立 MaxSum依然=20
     * ThisMax=(-4)+13=9 > MaxSum=20 不成立 MaxSum依然=20
     * ThisMax=(-4)+13+(-5)=4 > MaxSum=20 不成立 MaxSum依然=20
     * ThisMax=(-4)+13+(-5)+(-2)=2 > MaxSum=20 不成立 MaxSum依然=20
     *
     * 4、第一层循环的第4次循环和第3次循环类似
     * 操作如下：
     * ThisMax=13 > MaxSum=20 不成立 MaxSum依然=20
     * ThisMax=13+(-5)=8 > MaxSum=20 不成立 MaxSum依然=20
     * ThisMax=13+(-5)+(-2)=6 > MaxSum=20 不成立 MaxSum依然=20
     *
     * 5、第一层循环的第5次循环和第3次循环类似
     * 操作如下：
     * ThisMax=-5 > MaxSum=20 不成立 MaxSum依然=20
     * ThisMax=(-5)+(-2)=-7 > MaxSum=20 不成立 MaxSum依然=20
     *
     * 5、第一层循环的第6次循环和第3次循环类似
     * 操作如下：
     * ThisMax=-2 > MaxSum=20 不成立 MaxSum依然=20
     *
     * 此算法的最终结果就是20
     */
    int MaxSubqum(int A[], int N){
    
        int ThisSum,MaxSum = 0;
        //第一层循环
        for (int i = 0; i < N; ++i) {
            //第二层循环
            for (int l = i; l < N; ++l) {
                ThisSum = 0;
                //第三层循环
                for (int m = i; m <= l; ++m) {
                    ThisSum += A[m];
                }
                if (ThisSum>MaxSum){
                    MaxSum = ThisSum;
                }
            }
        }
        return MaxSum;
    }
    
    /*
     * 输入序列{-2,11,-4,13,-5,-2}
     * 最大子序列：{11,-4,13}和为20
     */
    int main() {
        //定义一个数组
        int A[6] =  {-2,11,-4,13,-5,-2};
        //数组中的元素为6
        int result = MaxSubqum(A,6);
        printf("result: %d\n",result);
        return 0;
    }

[Link 1]: https://zhuanlan.zhihu.com/p/25848393