最大子序和053 - 力扣（多种解法+c）

比眉伴天荒 2022-12-26 11:15 174阅读 0赞

### 目录 ###

*  1.最大子列和应用实例
 *   *  算法1：暴力求解
     *  算法2：进一步优化
     *  算法3：分而治之
     *  算法4：在线处理

# 1.最大子列和应用实例 #

给定N个整数的序列 A 1 , A 2 , … , A N \{ A\_1, A\_2, …, A\_N\} A1,A2,…,AN，求函数 f ( i , j ) = m a x \{ 0 , ∑ k = i j A k \} f(i,j) = max \\\{0,\\sum\_\{k=i\}^jA\_k\\\} f(i,j)=max\{ 0,∑k=ijAk\}的最大值。

> 对应力扣053最大子序和： 给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。 示例:  
> 输入: \[-2,1,-3,4,-1,2,1,-5,4\] 输出: 6 解释: 连续子数组 \[4,-1,2,1\] 的和最大为 6。  
> 链接：https://leetcode-cn.com/problems/maximum-subarray

> 命名规范问题：关于c语言的命名规范问题，对于c语言，一般而言**变量**命名采用驼峰规则，若变量采用多个单词拼成，首单词首字母小写，其余单词的首字母大写。对于**函数**，为了区分库函数与自己定义的函数，故自己定义的函数一般采用首字母大写。**宏定义**里面的变量全大写。

## 算法1：暴力求解 ##

int MaxubseqSum1(int *A, int N)
    { 
        int ThisSum, MaxSum = A[0];
        int i, j, k;
        for(i = 0; i < N; i++){  //i是子列左端位置
            for(j = i; j < N; j++){  //j是子列右端位置
                ThisSum = 0; //ThisSum是从A[i]至A[j]的子列和
                for(k = i; k <= j; k++) 
                    ThisSum += A[k];
                if(ThisSum > MaxSum) //如果刚得到的这个子列和更大
                    MaxSum = ThisSum; //更新结果
            }
        }
        return MaxSum;
    }

该算法的时间复杂度为 O ( n 3 ) O(n^3) O(n3).

## 算法2：进一步优化 ##

对于上述暴力求解，可以发现，第三层循环求子列和的时候，都是从i处开始计算到j处的子列和，接下来是从i处计算到j+1处，实际上我们不必每次从i开始，而从上一次得到的结果往后加一项就行，所以第三层循环没必要。

int MaxsubseqSum2(int *a, int n)
    { 
        int i, j, k;
        int thisSum, maxSum = a[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 ) O(n^2) O(n2)

## 算法3：分而治之 ##

对于时间复杂度为 O ( n 2 ) O(n^2) O(n2)的算法，我们希望对其加以改进使其复杂度达到 O ( n l o g n ) O(nlogn) O(nlogn)

> 分而治之也就是分治法，什么是分支法？如果我们有一个很复杂的大问题，很难直接解决它，但是我们发现可以把问题划分成子问题，如果子问题规模还是太大，并且它还可以继续划分，那就继续划分下去。直到这些子问题的规模已经很容易解决了，那么就把所有的子问题都解决，最后把所有的子问题合并，我们就得到复杂大问题的答案了。

对于该问题，我们可以将整个序列一分为二，递归的去解决左右两边的问题，分别求左半部分的最大子列和，右半部分的最大子列和。然后再去求横跨左右两部分的最大子列和，那么整体的最大子列和一定在三者之中产生。也就是三个子问题都能解决，那么答案就是三个结果的最大值。所以这就是先分，后治。

如下图所示：  
![在这里插入图片描述][20201204152137771.png]  
分析算法复杂度， T ( N ) = 2 T ( N / 2 ) + c N T(N) = 2T(N/2) + cN T(N)=2T(N/2)\+cN，因为一分为2，解决每半部分的时间复杂度为T(N/2),因为规模减半了，而计算横跨左右两半部分的最大子列和时扫描一次整个序列，故其复杂度为O(N).

因此其递推公式为：  
 T ( N ) = 2 T ( N / 2 ) + c N T(N) = 2T(N/2) + cN T(N)=2T(N/2)\+cN  
=  2 \[ 2 T ( N / 2 2 ) + c N / 2 \] + c N 2\[2T(N/2^2)+cN/2\]+cN 2\[2T(N/22)\+cN/2\]\+cN 当N/2^k = 1时，此时有T(1)=O(1)  
=  2 k O ( 1 ) + c k N 2^kO(1)+ckN 2kO(1)\+ckN 把N/2^k = 1代入  
= O ( N l o g N ) O(NlogN) O(NlogN)  
因此其时间复杂度为 O ( N l o g N ) O(NlogN) O(NlogN)

int Max(int a, int b, int c)
    { 
        return a > (b > c ? b : c) ? a : (b > c ? b : c);
    }
    int MaxSubseq(int *a, int left, int right)
    { 
        if(left == right)
            return a[left];
        int center = (left + right)/2;
        /* 分别找到左右最大子列和*/
        int leftSum = MaxSubseq(a, left, center);
        int rightSum = MaxSubseq(a, center + 1, right);
        /* 找到横跨左右两半部分的最大子列和*/
        int maxLeftBorderSum = a[center];
        int leftBorderSum = 0;
        for(int i = center; i >= left; i--){ 
            leftBorderSum += a[i];
            if(leftBorderSum > maxLeftBorderSum)
                maxLeftBorderSum = leftBorderSum;
        }
        int maxRightBorderSum = a[center + 1];
        int rightBorderSum = 0;
        for(int i = center + 1; i <= right; i++){ 
            rightBorderSum += a[i];
            if(rightBorderSum > maxRightBorderSum)
                maxRightBorderSum = rightBorderSum;
        }
        return Max(leftSum, rightSum, maxLeftBorderSum+maxRightBorderSum);
    }
    
    int MaxsubseqSum3(int *a, int n)
    { 
        return MaxSubseq(a, 0, n-1);
    
    }

另外需要注意的是，编程过程中判断相等的时候，可以将常数放在前面，防止由于书写错误而引起的错误，比如1=len，书写的时候少写了一个等号，而len=1就认为是赋值操作，没有问题，但是1=len就会报错了。

## 算法4：在线处理 ##

> 在线处理，在线的意思是指每输入一个数据就进行即时处理，在任何一个地方中止输入，算法都能正确给出当前的解。

int MaxsubseqSum4(int *a, int n)
    { 
        int thisSum = 0,maxSum = a[0];
        for(int i=0; i < n; i++){ 
            thisSum += a[i]; //向右累加
            if(thisSum > maxSum) //发现更大的和更新结果
                maxSum = thisSum;
            if(thisSum < 0) //如果为负数,则不能使后面的结果增大,放弃前面的和
                thisSum = 0;
    
        }
        return maxSum;
    }

[20201204152137771.png]: /images/20221120/8cac56ae1ee14fe0a4c3bf1a29c879a0.png